Алгоритм генерации всех возможных перестановок списка?

Question

Скажем, у меня есть список из n элементов, я знаю, что есть n! Возможные способы заказа этих элементов. Что такое алгоритм для генерации всех возможных упорядочений этого списка? Например, у меня есть список [a, b, c]. Алгоритм возвращает [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , а]].

Я читаю это здесь http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Но Википедия никогда не умела объяснять. Я мало что понимаю.

Answer 1

В следующем 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);
        }
    }
}

Answer 2

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

(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 это можно выразить кратко.

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

Answer 4

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

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

Answer 5

#!/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']

Answer 6

Вот рекурсивное решение в 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' не удалено).

Answer 7

Вот алгоритм на 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" 

Answer 8

Просто чтобы завершить, 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

Answer 9

Вот нерекурсивное решение в 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());
}

Answer 10

Самый простой способ объяснить это с помощью некоторого псевдокода

так

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

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