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

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

113 голосов
/ 26 апреля 2010

Скажем, у меня есть список из 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

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

Ответы [ 33 ]

92 голосов
/ 26 апреля 2010

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

Таким образом, со списком [1,2,3,4] генерируются все перестановки, начинающиеся с 1, затем все перестановки, начинающиеся с 2, затем 3, затем 4.

Это эффективно уменьшает проблему от поиска перестановок в списке из четырех элементов до списка из трех элементов. После сокращения до 2, а затем 1 списков предметов, все они будут найдены.
Пример, показывающий перестановки процессов с использованием 3 цветных шариков:
Red, green and blue coloured balls ordered permutations image (от https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)

24 голосов
/ 06 июля 2013

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

13 голосов
/ 18 мая 2014

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

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

  1. Для списка L размера n будет одинаковое количество решений, начиная с L 1 , L 2 ... 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;
            }

        }
    }
}
13 голосов
/ 26 сентября 2013

Ответ Википедии на «лексикографический порядок» кажется мне совершенно ясным в стиле кулинарной книги. Он ссылается на происхождение алгоритма XIV века!

Я только что написал быструю реализацию алгоритма Википедии на 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]
9 голосов
/ 01 мая 2013

Как сказал 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);
    }
}
8 голосов
/ 27 апреля 2014

Рекурсив всегда требует некоторых умственных усилий для поддержания. А для больших чисел факториал легко огромен, и переполнение стека легко станет проблемой.

Для небольших чисел (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

Конечно, теперь этот код логически более сложен, я оставлю его для чтения.

5 голосов
/ 11 января 2014

Если кто-то задается вопросом, как это сделать при перестановке в 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 )

3 голосов
/ 28 февраля 2014 
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); Просто, чтобы вы знали, вы можете сделать это с или без возврата

3 голосов
/ 18 апреля 2016

в 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);
3 голосов
/ 24 февраля 2014

Еще один в 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
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...