Программа для печати перестановок заданных элементов

Недавно я принимал участие в конкурсе по сертификации ACM. Это вопрос, который я не мог сделать в то время:

«Для массива целых чисел, содержащих n элементов, напишите программу для печати всех перестановок».

Скажите, пожалуйста, как это сделать. Есть ли какой-либо алгоритм для решения подобных вопросов?

предполагая, что повторений нет: просто измените каждый элемент со всеми возможными следующими элементами и рекурсивно вызовите функцию.

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; } 

Вы можете видеть код с вспомогательными функциями swap() и printArray() выполняющими базовый тестовый пример на ideone

Бонус : это похоже на идею перетасовки рыбаков-ятов , но здесь - попробуйте заменить элемент на i со случайно выбранным следующим элементом - вы меняете его со всеми из них - каждый за раз.

Рекурсивный подход должен преуспеть:

 If the list is empty Return the only possible permutation, an empty list. Else For each element of the list Put the element at the first place (ie swap it with the first element) (If the element is same as the first one, don't swap) Recursively find all the permutations of the rest of the list 

Этот алгоритм не будет генерировать повторяющиеся перестановки.

Вот реализация python:

 def permute(s): if len(s) == 0: return [[]] ret = [s[0:1] + x for x in permute(s[1:])] for i in range(1, len(s)): if s[i] == s[0]: continue s[0], s[i] = s[i], s[0] ret += [s[0:1] + x for x in permute(s[1:])] return ret s = [0, 1, 2, 3] for x in permute(s): print x 

Аналогичная вещь в C должна быть такой:

 void swap(char* str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } void permute(char *string, int start, int end) { if(start == end) { printf("%s\n", string); return; } permute(string, start + 1, end); int i; for(i = start + 1; i < end; i++) { if(string[start] == string[i]) continue; swap(string, start, i); permute(string, start + 1, end); swap(string, start, i); } } 

Вот итеративное решение:

Сначала отсортируйте массив.

  • Найти максимальный индекс ia [i + 1]. (если такой индекс не существует, осталось больше перестановок)

Найти максимальный индекс j

Поменяйте a [i] и [j].

Отмените a [i + 1] .. a [n-1] и перейдите к шагу *.

чтобы получить перестановку, вы должны использовать рекультивирование и откат, вы также можете решить ее с помощью грубой силы, но она становится сложной

  void swap(int *x1,int *x2) { int x=*x1; *x1=*x2; *x2=x; } void per(int *arr,int st,int ls) { int i=0; if(st==ls) { int k; for(k=0;k 
Interesting Posts
Давайте будем гением компьютера.