Скажем, у меня есть список n элементов, я знаю, что есть n! возможные способы упорядочения этих элементов. Что такое алгоритм для генерации всех возможных порядков этого списка? Например, у меня есть список [a, b, c]. Алгоритм возвращает [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].
Я читаю это здесь http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
Но Википедия никогда не умела объяснять. Я не очень понимаю.
В принципе, для каждого элемента слева направо все подстановки остальных элементов генерируются (и каждый добавляется с текущими элементами). Это можно сделать рекурсивно (или итеративно, если вам нравится боль) до тех пор, пока не будет достигнут последний элемент, в этот момент существует только один возможный порядок.
Итак, со списком [1,2,3,4] все перестановки, начинающиеся с 1, сгенерированы, то все перестановки, начинающиеся с 2, затем 3, затем 4.
Это эффективно уменьшает проблему с одного из поиска перестановок списка из четырех элементов в список из трех элементов. После сокращения до 2, а затем 1 списка элементов, все они будут найдены.
Пример, показывающий перестановки процессов с использованием 3 цветных шаров: 
(от https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)
Вот алгоритм в Python, который работает на месте в массиве:
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
Вы можете попробовать код для себя здесь: http://repl.it/J9v
Ответ Википедии на "лексикографический порядок" кажется мне совершенно явным в стике поваренной книги. Он ссылается на начало 14-го века для алгоритма!
Я только что написал краткую реализацию в Java из алгоритма Википедии в качестве проверки, и это не было проблемой. Но то, что у вас в вашем Q как пример, НЕ "перечисляет все перестановки", а "СПИСОК всех перестановок", поэтому википедия не поможет вам. Вам нужен язык, в котором списки перестановок могут быть построены. И поверьте мне, списки на несколько миллиардов долларов обычно не обрабатываются на императивных языках. Вам действительно нужен нестрогий функциональный язык программирования, в котором списки являются первоклассным объектом, чтобы вытащить материал, не доведя машину до жары смерти Вселенной.
Это легко. В стандартном Haskell или любом современном языке FP:
-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms [] = [ [] ]
и
-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits [] = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]
Здесь уже есть много хороших решений, но я хотел бы поделиться тем, как я решил эту проблему самостоятельно, и надеюсь, что это может быть полезно для тех, кто хотел бы также получить собственное решение.
После некоторого размышления над проблемой я придумал два следующих вывода:
L размера n будет равное количество решений, начиная с L 1, L 2... L n элементов списка. Поскольку в общем случае существуют перестановки n! списка размера n, мы получаем перестановки n! / n = (n-1)! в каждой группе.[a,b] и [b,a].Используя эти две простые идеи, я получил следующий алгоритм:
permute array
if array is of size 2
return first and second element as new array
return second and first element as new array
else
for each element in array
new subarray = array with excluded element
return element + permute subarray
Вот как я реализовал это в С#:
public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
if (input.Count == 2) // this are permutations of array of size 2
{
yield return new List<T>(input);
yield return new List<T> {input[1], input[0]};
}
else
{
foreach(T elem in input) // going through array
{
var rlist = new List<T>(input); // creating subarray = array
rlist.Remove(elem); // removing element
foreach(List<T> retlist in Permutate(rlist))
{
retlist.Insert(0,elem); // inserting the element at pos 0
yield return retlist;
}
}
}
}
Как сказал WhirlWind, вы начинаете с самого начала.
Вы меняете курсор с каждым оставшимся значением, включая сам курсор, все это новые экземпляры (я использовал int[] и array.clone() в примере).
Затем выполните перестановки во всех этих разных списках, указав, что курсор один вправо.
Если больше нет оставшихся значений (курсор находится в конце), распечатайте список. Это условие остановки.
public void permutate(int[] list, int pointer) {
if (pointer == list.length) {
//stop-condition: print or process number
return;
}
for (int i = pointer; i < list.length; i++) {
int[] permutation = (int[])list.clone();.
permutation[pointer] = list[i];
permutation[i] = list[pointer];
permutate(permutation, pointer + 1);
}
}
Рекурсивность всегда требует некоторых умственных усилий для поддержания. И для больших чисел факториал легко огромен, и переполнение стека будет легко проблемой.
Для небольших чисел (3 или 4, которые чаще всего встречаются), несколько циклов довольно просты и прямолинейны. Это неудачные ответы, когда петли не проголосовали.
Начнем с перечисления (а не перестановки). Просто прочитайте код как псевдо-perl-код.
$foreach $i1 in @list
$foreach $i2 in @list
$foreach $i3 in @list
print "$i1, $i2, $i3\n"
Перечисление чаще встречается, чем перестановка, но если требуется перестановка, просто добавьте условия:
$foreach $i1 in @list
$foreach $i2 in @list
$if $i2==$i1
next
$foreach $i3 in @list
$if $i3==$i1 or $i3==$i2
next
print "$i1, $i2, $i3\n"
Теперь, если вам действительно нужен общий метод для больших списков, мы можем использовать метод radix. Во-первых, рассмотрим проблему перечисления:
[email protected]
my @radix
$for $i=0:$n
$radix[$i]=0
$while 1
my @temp
$for $i=0:$n
push @temp, $list[$radix[$i]]
print join(", ", @temp), "\n"
$call radix_increment
subcode: radix_increment
$i=0
$while 1
$radix[$i]++
$if $radix[$i]==$n
$radix[$i]=0
$i++
$else
last
$if $i>=$n
last
Приращение радикса - это, по сути, подсчет числа (в базе числа элементов списка).
Теперь, если вам нужна перестановка, просто добавьте проверки внутри цикла:
subcode: check_permutation
my @check
my $flag_dup=0
$for $i=0:$n
$check[$radix[$i]]++
$if $check[$radix[$i]]>1
$flag_dup=1
last
$if $flag_dup
next
Изменить: приведенный выше код должен работать, но для перестановки radix_increment может быть расточительным. Поэтому, если время является практической проблемой, мы должны изменить radix_increment на permute_inc:
subcode: permute_init
$for $i=0:$n
$radix[$i]=$i
subcode: permute_inc
$max=-1
$for $i=$n:0
$if $max<$radix[$i]
$max=$radix[$i]
$else
$for $j=$n:0
$if $radix[$j]>$radix[$i]
$call swap, $radix[$i], $radix[$j]
break
$j=$i+1
$k=$n-1
$while $j<$k
$call swap, $radix[$j], $radix[$k]
$j++
$k--
break
$if $i<0
break
Конечно, теперь этот код логически более сложный, я уйду для чтения.
Если кто-то задается вопросом, как это сделать в перестановке в javascript.
Идея/псевдокод
например. 'a' + перестановка (bc). перестановка bc будет bc и cb. Теперь добавьте эти два, даст abc, acb. аналогично, выбор b + permute (ac) будет содержать bac, bca... и продолжать идти.
теперь посмотрите код
function permutations(arr){
var len = arr.length,
perms = [],
rest,
picked,
restPerms,
next;
//for one or less item there is only one permutation
if (len <= 1)
return [arr];
for (var i=0; i<len; i++)
{
//copy original array to avoid changing it while picking elements
rest = Object.create(arr);
//splice removed element change array original array(copied array)
//[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
picked = rest.splice(i, 1);
//get the permutation of the rest of the elements
restPerms = permutations(rest);
// Now concat like a+permute(bc) for each
for (var j=0; j<restPerms.length; j++)
{
next = picked.concat(restPerms[j]);
perms.push(next);
}
}
return perms;
}
Потратьте время, чтобы понять это. Я получил этот код из (pertumation в JavaScript)
Другой в Python, он не на месте, как @cdiggins, но я думаю, что это легче понять
def permute(num):
if len(num) == 2:
# get the permutations of the last 2 numbers by swapping them
yield num
num[0], num[1] = num[1], num[0]
yield num
else:
for i in range(0, len(num)):
# fix the first number and get the permutations of the rest of numbers
for perm in permute(num[0:i] + num[i+1:len(num)]):
yield [num[i]] + perm
for p in permute([1, 2, 3, 4]):
print p
Я подумывал написать код для получения перестановок любого заданного целого числа любого размера, то есть, предоставляя число 4567, мы получаем все возможные перестановки до 7654... Поэтому я работал над ним и нашел алгоритм и, наконец, реализовал это, Вот код, написанный на "c". Вы можете просто скопировать его и запустить на любом компиляторе с открытым исходным кодом. Но некоторые недостатки ждут отладки. Пожалуйста, оцените.
Код:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
//PROTOTYPES
int fact(int); //For finding the factorial
void swap(int*,int*); //Swapping 2 given numbers
void sort(int*,int); //Sorting the list from the specified path
int imax(int*,int,int); //Finding the value of imax
int jsmall(int*,int); //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm(); //All the important tasks are done in this function
int n; //Global variable for input OR number of digits
void main()
{
int c=0;
printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}
void perm(int c){
int *p; //Pointer for allocating separate memory to every single entered digit like arrays
int i, d;
int sum=0;
int j, k;
long f;
n = 0;
while(c != 0) //this one is for calculating the number of digits in the entered number
{
sum = (sum * 10) + (c % 10);
n++; //as i told at the start of loop
c = c / 10;
}
f = fact(n); //It gives the factorial value of any number
p = (int*) malloc(n*sizeof(int)); //Dynamically allocation of array of n elements
for(i=0; sum != 0 ; i++)
{
*(p+i) = sum % 10; //Giving values in dynamic array like 1234....n separately
sum = sum / 10;
}
sort(p,-1); //For sorting the dynamic array "p"
for(c=0 ; c<f/2 ; c++) { //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)
for(k=0 ; k<n ; k++)
printf("%d",p[k]); //Loop for printing one of permutations
printf("\n");
i = d = 0;
i = imax(p,i,d); //provides the max i as per algo (i am restricted to this only)
j = i;
j = jsmall(p,j); //provides smallest i val as per algo
swap(&p[i],&p[j]);
for(k=0 ; k<n ; k++)
printf("%d",p[k]);
printf("\n");
i = d = 0;
i = imax(p,i,d);
j = i;
j = jsmall(p,j);
swap(&p[i],&p[j]);
sort(p,i);
}
free(p); //Deallocating memory
}
int fact (int a)
{
long f=1;
while(a!=0)
{
f = f*a;
a--;
}
return f;
}
void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}
void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
for(j=i+1 ; j<n ; j++)
{
if(*(p+i) > *(p+j))
{
temp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = temp;
}
}
}
}
int imax(int *p, int i , int d)
{
while(i<n-1 && d<n-1)
{
if(*(p+d) < *(p+d+1))
{
i = d;
d++;
}
else
d++;
}
return i;
}
int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
if (p[i]<small && p[i]>p[k])
{
small = p[i];
j = i;
}
}
return j;
}
void permutate(char[] x, int i, int n){
x=x.clone();
if (i==n){
System.out.print(x);
System.out.print(" ");
counter++;}
else
{
for (int j=i; j<=n;j++){
// System.out.print(temp); System.out.print(" "); //Debugger
swap (x,i,j);
// System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
permutate(x,i+1,n);
// swap (temp,i,j);
}
}
}
void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}
Я создал этот. основанный на исследованиях перестановка (qwe, 0, qwe.length-1); Просто, чтобы вы знали, вы можете делать это с возвратом или без него
Здесь игрушечный Ruby-метод, который работает как #permutation.to_a, который может быть более разборчивым для сумасшедших людей. Это hella медленно, но также и 5 строк.
def permute(ary)
return [ary] if ary.size <= 1
ary.collect_concat.with_index do |e, i|
rest = ary.dup.tap {|a| a.delete_at(i) }
permute(rest).collect {|a| a.unshift(e) }
end
end
Я написал это рекурсивное решение в ANSI C. Каждое выполнение функции Permutate предоставляет одну другую перестановку, пока все не будет завершено. Глобальные переменные также могут использоваться для фактов и подсчетов переменных.
#include <stdio.h>
#define SIZE 4
void Rotate(int vec[], int size)
{
int i, j, first;
first = vec[0];
for(j = 0, i = 1; i < size; i++, j++)
{
vec[j] = vec[i];
}
vec[j] = first;
}
int Permutate(int *start, int size, int *count)
{
static int fact;
if(size > 1)
{
if(Permutate(start + 1, size - 1, count))
{
Rotate(start, size);
}
fact *= size;
}
else
{
(*count)++;
fact = 1;
}
return !(*count % fact);
}
void Show(int vec[], int size)
{
int i;
printf("%d", vec[0]);
for(i = 1; i < size; i++)
{
printf(" %d", vec[i]);
}
putchar('\n');
}
int main()
{
int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
int count = 0;
do
{
Show(vec, SIZE);
} while(!Permutate(vec, SIZE, &count));
putchar('\n');
Show(vec, SIZE);
printf("\nCount: %d\n\n", count);
return 0;
}
Вот код в Python для печати всех возможных перестановок списка:
def next_perm(arr):
# Find non-increasing suffix
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return False
# Find successor to pivot
j = len(arr) - 1
while arr[j] <= arr[i - 1]:
j -= 1
arr[i - 1], arr[j] = arr[j], arr[i - 1]
# Reverse suffix
arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
print arr
return True
def all_perm(arr):
a = next_perm(arr)
while a:
a = next_perm(arr)
arr = raw_input()
arr.split(' ')
arr = map(int, arr)
arr.sort()
print arr
all_perm(arr)
Я использовал алгоритм лексикографического порядка, чтобы получить все возможные перестановки, но рекурсивный алгоритм более эффективен. Здесь вы можете найти код для рекурсивного алгоритма: Перестановки рекурсии Python
Версия Java
/**
* @param uniqueList
* @param permutationSize
* @param permutation
* @param only Only show the permutation of permutationSize,
* else show all permutation of less than or equal to permutationSize.
*/
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
if (permutation == null) {
assert 0 < permutationSize && permutationSize <= uniqueList.size();
permutation = new ArrayList<>(permutationSize);
if (!only) {
System.out.println(Arrays.toString(permutation.toArray()));
}
}
for (int i : uniqueList) {
if (permutation.contains(i)) {
continue;
}
permutation.add(i);
if (!only) {
System.out.println(Arrays.toString(permutation.toArray()));
} else if (permutation.size() == permutationSize) {
System.out.println(Arrays.toString(permutation.toArray()));
}
if (permutation.size() < permutationSize) {
my_permutationOf(uniqueList, permutationSize, permutation, only);
}
permutation.remove(permutation.size() - 1);
}
}
например.
public static void main(String[] args) throws Exception {
my_permutationOf(new ArrayList<Integer>() {
{
add(1);
add(2);
add(3);
}
}, 3, null, true);
}
вывод:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
в PHP
$set=array('A','B','C','D');
function permutate($set) {
$b=array();
foreach($set as $key=>$value) {
if(count($set)==1) {
$b[]=$set[$key];
}
else {
$subset=$set;
unset($subset[$key]);
$x=permutate($subset);
foreach($x as $key1=>$value1) {
$b[]=$value.' '.$value1;
}
}
}
return $b;
}
$x=permutate($set);
var_export($x);
// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}
/* Driver program to test above functions */
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}
Ссылка: Geeksforgeeks.org
public class PermutationGenerator
{
private LinkedList<List<int>> _permutationsList;
public void FindPermutations(List<int> list, int permutationLength)
{
_permutationsList = new LinkedList<List<int>>();
foreach(var value in list)
{
CreatePermutations(value, permutationLength);
}
}
private void CreatePermutations(int value, int permutationLength)
{
var node = _permutationsList.First;
var last = _permutationsList.Last;
while (node != null)
{
if (node.Value.Count < permutationLength)
{
GeneratePermutations(node.Value, value, permutationLength);
}
if (node == last)
{
break;
}
node = node.Next;
}
List<int> permutation = new List<int>();
permutation.Add(value);
_permutationsList.AddLast(permutation);
}
private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
{
if (permutation.Count < permutationLength)
{
List<int> copyOfInitialPermutation = new List<int>(permutation);
copyOfInitialPermutation.Add(value);
_permutationsList.AddLast(copyOfInitialPermutation);
List<int> copyOfPermutation = new List<int>();
copyOfPermutation.AddRange(copyOfInitialPermutation);
int lastIndex = copyOfInitialPermutation.Count - 1;
for (int i = lastIndex;i > 0;i--)
{
int temp = copyOfPermutation[i - 1];
copyOfPermutation[i - 1] = copyOfPermutation[i];
copyOfPermutation[i] = temp;
List<int> perm = new List<int>();
perm.AddRange(copyOfPermutation);
_permutationsList.AddLast(perm);
}
}
}
public void PrintPermutations(int permutationLength)
{
int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
Console.WriteLine("The number of permutations is " + count);
}
}
В Scala
def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)
def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {
var result: List[List[Int]] = Nil
for (i ← n if (!(acc contains (i))))
if (acc.size == n.size-1)
result = (i :: acc) :: result
else
result = result ::: permutationeAcc(n, i :: acc)
result
}
это версия java для перестановки
public class Permutation {
static void permute(String str) {
permute(str.toCharArray(), 0, str.length());
}
static void permute(char [] str, int low, int high) {
if (low == high) {
System.out.println(str);
return;
}
for (int i=low; i<high; i++) {
swap(str, i, low);
permute(str, low+1, high);
swap(str, low, i);
}
}
static void swap(char [] array, int i, int j) {
char t = array[i];
array[i] = array[j];
array[j] = t;
}
}
Здесь реализована реализация ColdFusion (требуется CF10 из-за аргумента merge для ArrayAppend()):
public array function permutateArray(arr){
if (not isArray(arguments.arr) ) {
return ['The ARR argument passed to the permutateArray function is not of type array.'];
}
var len = arrayLen(arguments.arr);
var perms = [];
var rest = [];
var restPerms = [];
var rpLen = 0;
var next = [];
//for one or less item there is only one permutation
if (len <= 1) {
return arguments.arr;
}
for (var i=1; i <= len; i++) {
// copy the original array so as not to change it and then remove the picked (current) element
rest = arraySlice(arguments.arr, 1);
arrayDeleteAt(rest, i);
// recursively get the permutation of the rest of the elements
restPerms = permutateArray(rest);
rpLen = arrayLen(restPerms);
// Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
for (var j=1; j <= rpLen; j++) {
// for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
next = arraySlice(arguments.arr, i, 1);
arrayAppend(next, restPerms[j], true);
arrayAppend(perms, next);
}
}
return perms;
}
Основано на вышеупомянутом решении KhanSharp js.
В следующем решении Java мы воспользуемся тем, что Strings являются неизменяемыми, чтобы избежать клонирования набора результатов на каждой итерации.
Вход будет строкой, скажем, "abc", и на выходе будут все возможные перестановки:
abc
acb
bac
bca
cba
cab
public static void permute(String s) {
permute(s, 0);
}
private static void permute(String str, int left){
if(left == str.length()-1) {
System.out.println(str);
} else {
for(int i = left; i < str.length(); i++) {
String s = swap(str, left, i);
permute(s, left+1);
}
}
}
private static String swap(String s, int left, int right) {
if (left == right)
return s;
String result = s.substring(0, left);
result += s.substring(right, right+1);
result += s.substring(left+1, right);
result += s.substring(left, left+1);
result += s.substring(right+1);
return result;
}
Такой же подход может применяться к массивам (вместо строки):
public static void main(String[] args) {
int[] abc = {1,2,3};
permute(abc, 0);
}
public static void permute(int[] arr, int index) {
if (index == arr.length) {
System.out.println(Arrays.toString(arr));
} else {
for (int i = index; i < arr.length; i++) {
int[] permutation = arr.clone();
permutation[index] = arr[i];
permutation[i] = arr[index];
permute(permutation, index + 1);
}
}
}
Я знаю, что это очень старая и даже не относящаяся к теме тема stackoverflow, но я все же хотел внести свой вклад в дружественный ответ javascript по той простой причине, что он запускается в вашем браузере.
Я также добавил контрольную точку директивы debugger, чтобы вы могли выполнить код (требуется хром), чтобы увидеть, как работает этот алгоритм. Откройте консоль dev в chrome (F12 в окнах или CMD + OPTION + I на Mac), а затем нажмите "Запустить фрагмент кода". Это реализует тот же точный алгоритм, который @WhirlWind представил в своем ответе.
Ваш браузер должен приостановить выполнение в директиве debugger. Используйте F8, чтобы продолжить выполнение кода.
function permute(rest, prefix = []) {
if (rest.length === 0) {
return [prefix];
}
return (rest
.map((x, index) => {
const oldRest = rest;
const oldPrefix = prefix;
// the `...` destructures the array into single values flattening it
const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
const newPrefix = [...prefix, x];
debugger;
const result = permute(newRest, newPrefix);
return result;
})
// this step flattens the array of arrays returned by calling permute
.reduce((flattened, arr) => [...flattened, ...arr], [])
);
}
console.log(permute([1, 2, 3]));Это мое решение на Java:
public class CombinatorialUtils {
public static void main(String[] args) {
List<String> alphabet = new ArrayList<>();
alphabet.add("1");
alphabet.add("2");
alphabet.add("3");
alphabet.add("4");
for (List<String> strings : permutations(alphabet)) {
System.out.println(strings);
}
System.out.println("-----------");
for (List<String> strings : combinations(alphabet)) {
System.out.println(strings);
}
}
public static List<List<String>> combinations(List<String> alphabet) {
List<List<String>> permutations = permutations(alphabet);
List<List<String>> combinations = new ArrayList<>(permutations);
for (int i = alphabet.size(); i > 0; i--) {
final int n = i;
combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
}
return combinations;
}
public static <T> List<List<T>> permutations(List<T> alphabet) {
ArrayList<List<T>> permutations = new ArrayList<>();
if (alphabet.size() == 1) {
permutations.add(alphabet);
return permutations;
} else {
List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
T addedElem = alphabet.get(0);
for (int i = 0; i < alphabet.size(); i++) {
for (List<T> permutation : subPerm) {
int index = i;
permutations.add(new ArrayList<T>(permutation) {{
add(index, addedElem);
}});
}
}
}
return permutations;
}
}
Вы действительно не можете говорить о решении проблемы перенастройки в рекурсии, не публикуя реализацию на языке (диалекте), который впервые предложил идею. Итак, для полноты, вот один из способов, которые можно сделать на Схеме.
(define (permof wd)
(cond ((null? wd) '())
((null? (cdr wd)) (list wd))
(else
(let splice ([l '()] [m (car wd)] [r (cdr wd)])
(append
(map (lambda (x) (cons m x)) (permof (append l r)))
(if (null? r)
'()
(splice (cons m l) (car r) (cdr r))))))))
вызывая (permof (list "foo" "bar" "baz")), мы получим:
'(("foo" "bar" "baz")
("foo" "baz" "bar")
("bar" "foo" "baz")
("bar" "baz" "foo")
("baz" "bar" "foo")
("baz" "foo" "bar"))
Я не буду вдаваться в детали алгоритма, потому что это было достаточно объяснено в других сообщениях. Идея такая же.
Однако рекурсивные проблемы, как правило, гораздо сложнее моделировать и думать в деструктивной среде, такой как Python, C и Java, тогда как в Lisp или ML она может быть сжато выражена.
Вот рекурсивное решение в PHP. Сообщение WhirlWind точно описывает логику. Стоит упомянуть, что генерация всех перестановок выполняется в факториальное время, поэтому было бы неплохо использовать итеративный подход.
public function permute($sofar, $input){
for($i=0; $i < strlen($input); $i++){
$diff = strDiff($input,$input[$i]);
$next = $sofar.$input[$i]; //next contains a permutation, save it
$this->permute($next, $diff);
}
}
Функция strDiff принимает две строки, s1 и s2, и возвращает новую строку со всем в s1 без элементов в s2 (дублирует вопрос). Итак, strDiff('finish','i') = > 'fnish' (второй "i" не удаляется).
Вот алгоритм в R, если кто-то должен избегать загрузки дополнительных библиотек, подобных мне.
permutations <- function(n){
if(n==1){
return(matrix(1))
} else {
sp <- permutations(n-1)
p <- nrow(sp)
A <- matrix(nrow=n*p,ncol=n)
for(i in 1:n){
A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
}
return(A)
}
}
Пример использования:
> matrix(letters[permutations(3)],ncol=3)
[,1] [,2] [,3]
[1,] "a" "b" "c"
[2,] "a" "c" "b"
[3,] "b" "a" "c"
[4,] "b" "c" "a"
[5,] "c" "a" "b"
[6,] "c" "b" "a"
#!/usr/bin/env python
import time
def permutations(sequence):
# print sequence
unit = [1, 2, 1, 2, 1]
if len(sequence) >= 4:
for i in range(4, (len(sequence) + 1)):
unit = ((unit + [i - 1]) * i)[:-1]
# print unit
for j in unit:
temp = sequence[j]
sequence[j] = sequence[0]
sequence[0] = temp
yield sequence
else:
print 'You can use PEN and PAPER'
# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']
print s
z = permutations(s)
try:
while True:
# time.sleep(0.0001)
print next(z)
except StopIteration:
print 'Done'
['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']
Решение оболочки Bourne - в общей сложности четыре строки (без теста для случая с параметром):
test $# -eq 1 && echo "$1" && exit
for i in $*; do
$0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done
Это рекурсивный код для java, идея состоит в том, чтобы иметь префикс, который добавляет остальные символы:
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str);
}
}
Пример:
Вход = "ABC"; Выход:
ABC ACB BAC BCA ТАКСИ CBA
Чтобы быть полным, С++
#include <iostream>
#include <algorithm>
#include <string>
std::string theSeq = "abc";
do
{
std::cout << theSeq << endl;
}
while (std::next_permutation(theSeq.begin(), theSeq.end()));
...
abc
acb
bac
bca
cab
cba