程序打印特定元素的排列 [英] Program to print permutations of given elements
问题描述
我最近在ACM认证的编程竞赛的一部分。这是一个我不能这样做在当时的问题是:
I recently took part in ACM certified programming competition. This is the question which I could not do at that time:
由于有n个元素整数数组,编写一个程序来打印所有的排列组合。
"Given an array of integers having n elements, write a program to print all the permutations."
请告诉我该怎么做这个问题。是否有任何的算法来做这样的问题吗?
Please tell me how to do this question. Is there any algorithm to do this kind of questions?
推荐答案
假设没有重复:只要改变每个元素与所有可能的下列元素,并递归调用函数
assuming there are no repeats: just change each element with all possible following elements, and recursively invoke the function.
void permute(int *array,int i,int length) {
if (length == i){
printArray(array,length);
return;
}
int j = i;
for (j = i; j < length; j++) {
swap(array+i,array+j);
permute(array,i+1,length);
swap(array+i,array+j);
}
return;
}
您可以看到code与辅助的功能交换()
和 printArray()
执行与一基本的测试案例在 ideone
You can see the code with auxilary functions swap()
and printArray()
performing with a basic test case at ideone
奖金:这是类似于费雪耶茨洗牌的想法< /一>,但在这里 - 这一翻译到我
与随机选择的下一个元素 - 你与他们交换了它 - 每一次
Bonus: This is similar to the idea of fisher-yates shuffle, but in here - intead to swapping the element at i
with randomly chosen following element - you swap it with all of them - each at a time.
这篇关于程序打印特定元素的排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!