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

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

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

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

4 Solutions collect form web for “Программа для печати перестановок заданных элементов”

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

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 
  • Обнаружение цели в программном обеспечении на C ++
  • Алгоритм поиска всех путей в сетке NxN
  • Реализация алгоритма Хой Шамоса с помощью C #
  • C # Точка в многоугольнике
  • Есть ли алгоритм, который говорит о семантическом сходстве двух фраз
  • Как получить пересечение между двумя массивами как новый массив?
  • Алгоритм упрощения десятичных дробей
  • O (nlogn) Алгоритм. Найдите три равномерно распределенных внутри двоичной строки.
  • расчет високосного года
  • Как определить BPM песни в php
  • Программирование Загадка: как вы можете перевести имя столбца Excel в число?
  • Давайте будем гением компьютера.