По сути, для каждого элемента слева направо генерируются все перестановки оставшихся элементов (и каждый добавляется с текущими элементами). Это можно делать рекурсивно (или итеративно, если вам нравится боль), пока не будет достигнут последний элемент, и в этот момент существует только один возможный порядок.

Итак, со списком [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

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

Поразмыслив над проблемой, я пришел к двум следующим выводам:

1. Для списка L размера n будет одинаковое количество решений, начиная с L ₁, L ₂ ... L _n элементов список. Так как всего существует n! перестановок списка размера n, мы получаем n! / n = (n-1)! перестановок в каждой группе.
2. В списке из 2 элементов всего 2 перестановки => [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

Вот как я реализовал это на C #:

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

        }
    }
}

Ответ Википедии на «лексикографический порядок» мне кажется совершенно ясным в стиле поваренной книги. Он ссылается на происхождение алгоритма 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]

Как сказал 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. Сначала рассмотрим проблему перечисления:

$n=@list
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.

Идея / псевдокод

1. выбирайте по одному элементу за раз
2. переставить остальную часть элемента, а затем добавить выбранный элемент ко всей перестановке

Например. 'а' + перестановка (до н.э.). перестановка 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;
}

Не торопитесь, чтобы понять это. Я получил этот код из (пертумации в JavaScript)

Я написал это рекурсивное решение на ANSI C. Каждое выполнение функции Permutate обеспечивает одну другую перестановку, пока все не будут завершены. Глобальные переменные также могут использоваться для переменных fact и count.

#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, его нет, как у @ 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, который может быть более понятным для сумасшедших. Это чертовски медленно, но тоже 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

Версия 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);
    }
}

E.g.

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

это версия 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;
    }
}

Вот код на 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

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

Вот реализация ColdFusion (требуется CF10 из-за аргумента слияния для 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 выше.

Я знаю, что это очень-очень старый и даже не по теме в сегодняшнем stackoverflow, но я все же хотел внести дружественный ответ javascript по той простой причине, что он работает в вашем браузере.

Я также добавил точку останова директивы debugger, чтобы вы могли пройти через код (требуется хром), чтобы увидеть, как работает этот алгоритм. Откройте консоль разработчика в Chrome (F12 в Windows или 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 мы используем тот факт, что строки неизменяемы, чтобы избежать клонирования набора результатов при каждой итерации.

На входе будет строка, скажем «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);
        }
    }
}

Это мое решение на 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;
    }
}

Вы не можете говорить о решении проблемы пермутации в рекурсии без публикации реализации на (диалекте) языка, который был пионером этой идеи. Итак, для полноты, вот один из способов, который можно сделать в Scheme.

(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" 

Для полноты: C ++

#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

Вот нерекурсивное решение на C ++, которое обеспечивает следующую перестановку в порядке возрастания, аналогично функциональности, предоставляемой std :: next_permutation:

void permute_next(vector<int>& v)
{
  if (v.size() < 2)
    return;

  if (v.size() == 2)
  { 
    int tmp = v[0];
    v[0] = v[1];
    v[1] = tmp;
    return;
  }

  // Step 1: find first ascending-ordered pair from right to left
  int i = v.size()-2;
  while(i>=0)
  { 
    if (v[i] < v[i+1])
      break;
    i--;
  }
  if (i<0) // vector fully sorted in descending order (last permutation)
  {
    //resort in ascending order and return
    sort(v.begin(), v.end());
    return;
  }

  // Step 2: swap v[i] with next higher element of remaining elements
  int pos = i+1;
  int val = v[pos];
  for(int k=i+2; k<v.size(); k++)
    if(v[k] < val && v[k] > v[i])
    {
      pos = k;
      val = v[k];
    }
  v[pos] = v[i];
  v[i] = val;

  // Step 3: sort remaining elements from i+1 ... end
  sort(v.begin()+i+1, v.end());
}

Это создает их по одному без составления списка - тот же конечный результат, что и ответ Мариоса Чоудари (или просто вызов C ++ nextPermute, как отмечает Андерс). Но это перестроенный алгоритм Heap (нерекурсивная версия) и класс для сохранения контекста. Используется в качестве:

P5=new genPermutes_t(5); // P5.P is now [0,1,2,3,4]
while(!P5.isDone()) {
  // use P5.P here
  P5.next();
}

Код написан на C # без одобрения. Переменные взяты из псевдокода Heap, к которому также относятся комментарии:

public class genPermutes_t {
  public int[] P; // the current permuation

  private int n, i; // vars from the original algorithm
  private int[] c; // ditto

  public genPermutes_t(int count) {
    // init algorithm:
    n=count;
    i=0;
    c=new int[n];
    for(int j=0;j<n;j++) c[j]=0;

    // start current permutation as 0,1 ... n-1:
    P=new int[n];
    for(int j=0;j<n;j++) P[j]=j;
  }

  public bool isDone() {
    return i>=n; // condition on the original while loop
  }

  public void next() {
    // the part of the loop that spins until done or ready for next permute:
    while(i<n && c[i]>=i) {
      c[i]=0;
      i++;
    }
    // pulled from inside loop -- the part that makes next permute:
    if(i<n) { // if not done
      if(i%2==0) swap(0,i);
      else swap(c[i], i);
      // "print P" removed. User will simply examine it
      c[i]+=1;
      i=0;
    }
  }

  private void swap(int i1, int i2) {int tmp=P[i1]; P[i1]=P[i2]; P[i2]=tmp;}
}

В языке C создайте единую матрицу (беззнаковый символ), чтобы быстро и легко получить доступ ко всем перестановкам от 1 до 6. На основе кода из https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/.

void swap(unsigned char* a, unsigned char* b)
{
    unsigned char t;

    t = *b;
    *b = *a;
    *a = t;
}

void print_permutations(unsigned char a[], unsigned char n)
{
    // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
    for (int i = 0; i < n; i++)
    {
        assert(a[i] < n);
        printf("%d ", a[i]);
    }
    printf("\n");
}

// Generating permutation using Heap Algorithm 
void generate_permutations(unsigned char (**permutations)[6], unsigned char a[], int size, int n)
{
    // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
    // if size becomes 1 then prints the obtained permutation 
    if (size == 1)
    {
        memcpy(*permutations, a, n);
        *permutations += 1;
    }
    else
    {
        for (int i = 0; i < size; i++)
        {
            generate_permutations(permutations, a, size - 1, n);

            // if size is odd, swap first and last element
            if (size & 1)
                swap(a, a + size - 1);

            // If size is even, swap ith and last element
            else
                swap(a + i, a + size - 1);
        }
    }
}

int main()
{
    unsigned char permutations[720][6]; // easily access all permutations from 1 to 6
    unsigned char suit_length_indexes[] = { 0, 1, 2, 3, 4, 5 };
    assert(sizeof(suit_length_indexes) == sizeof(permutations[0]));
    unsigned char(*p)[sizeof(suit_length_indexes)] = permutations;
    generate_permutations(&p, suit_length_indexes, sizeof(suit_length_indexes), sizeof(suit_length_indexes));
    for (int i = 0; i < sizeof(permutations) / sizeof(permutations[0]); i++)
        print_permutations(permutations[i], sizeof(suit_length_indexes));
    return 0;
}

Решение оболочки Борна - всего четыре строки (без проверки отсутствия параметров):

test $# -eq 1 && echo "$1" && exit
for i in $*; do
  $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done

Самый простой способ объяснить это - использовать псевдокод

so

list of 1, 2 ,3
for each item in list
    templist.Add(item)
    for each item2 in list
        if item2 is Not item
            templist.add(item)
               for each item3 in list
                   if item2 is Not item
                      templist.add(item)

                   end if
               Next
            end if

    Next
    permanentListofPermutaitons,add(templist)
    tempList.Clear()
Next

Очевидно, что это не самый гибкий способ сделать это, и выполнение его рекурсивно было бы намного более функциональным, потому что мой усталый мозг в воскресенье вечером не хочет думать об этом в данный момент. Если к утру рекурсивную версию никто не выставит, я ее сделаю.