[algorithm] 목록의 가능한 모든 순열을 생성하는 알고리즘?

재귀는 항상 유지하기 위해 약간의 정신적 노력이 필요합니다. 그리고 큰 숫자의 경우 팩토리얼은 쉽게 거대하고 스택 오버플로가 쉽게 문제가됩니다.

작은 숫자 (대부분 발생하는 3 또는 4)의 경우 다중 루프는 매우 간단하고 간단합니다. 루프가있는 불행한 답변이 투표되지 않았습니다.

(순열이 아닌) 열거부터 시작하겠습니다. 코드를 의사 펄 코드로 읽으십시오.

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

이제 큰 목록에 대해 잠재적으로 일반적인 방법이 필요한 경우 기수 방법을 사용할 수 있습니다. 먼저 열거 문제를 고려하십시오.

$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

물론 이제이 코드는 논리적으로 더 복잡하므로 독자의 연습을 위해 떠날 것입니다.

답변

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