반응형
목록의 가능한 모든 순열을 생성하는 알고리즘?
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
그러나 Wikipedia는 결코 잘 설명하지 못했습니다. 나는 그것을 많이 이해하지 못한다.
기본적으로 왼쪽에서 오른쪽으로 각 항목에 대해 나머지 항목의 모든 순열이 생성됩니다 (각 항목에 현재 요소가 추가됨). 이것은 마지막 항목에 도달 할 때까지 재귀 적으로 (또는 통증이있는 경우 반복적으로) 수행 될 수 있으며,이 시점에서 하나의 가능한 주문 만 있습니다.
따라서리스트 [1,2,3,4]를 사용하면 1로 시작하는 모든 순열이 생성 된 다음 2, 3, 4로 시작하는 모든 순열이 생성됩니다.
이렇게하면 4 개 항목 목록의 순열을 찾는 중 하나에서 3 개 항목 목록으로 문제를 효과적으로 줄일 수 있습니다. 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
여기에는 이미 좋은 해결책이 많이 있지만이 문제를 어떻게 해결했는지 공유하고 이것이 자신의 해결책을 도출하려는 사람에게 도움이되기를 바랍니다.
문제에 대해 숙고 한 후에 두 가지 결론을 내 렸습니다.
L크기 목록 의 경우 목록 의nL 1 , L 2 ... L n 요소로 시작하는 동일한 수의 솔루션이 있습니다 . 전체적으로n!size 목록의 순열이 있으므로 각 그룹에서 순열을n얻습니다n! / n = (n-1)!.- 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;
}
}
}
}
"사전 순서"에 대한 Wikipedia의 답변은 요리 책 스타일로 완벽하게 나타납니다. 알고리즘의 기원은 14 세기입니다!
방금 Wikipedia 알고리즘의 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, 대부분 발생)의 경우 여러 루프가 매우 간단하고 간단합니다. 루프와 함께 유감스럽게도 답변을 얻지 못했습니다.
순열 대신 열거로 시작합시다. 코드를 의사 펄 코드로 읽으십시오.
$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
물론이 코드는 논리적으로 더 복잡합니다. 독자의 연습을 위해 떠날 것입니다.
누구나 자바 스크립트에서 순열을 수행하는 방법을 궁금해합니다.
아이디어 / 의사 코드
- 한 번에 하나의 요소를 선택
- 나머지 요소를 치환하고 선택한 요소를 모든 순열에 추가
예를 들어. 'a'+ permute (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;
}
이것을 이해하기 위해 시간을 내십시오. 이 코드를 얻었습니다 (JavaScript의 순열 )
파이썬의 또 다른 하나는 @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); 알다시피 역 추적 유무에 관계없이 할 수 있습니다.
#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
이 재귀 솔루션을 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;
}
자바 버전
/**
* @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
다음은 목록에서 가능한 모든 순열을 인쇄하는 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 재귀 순열
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);
}
}
스칼라
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
}
이것은 순열에 대한 자바 버전입니다
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에 대한 구현입니다 (ArrayAppend ()의 merge 인수로 인해 CF10 필요).
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 솔루션을 기반으로합니다.
나는 이것이 오늘날의 스택 오버 플로우에서 매우 오래되고 심지어 주제가 아닌 것을 알고 있지만 여전히 브라우저에서 실행되는 간단한 이유로 친근한 자바 스크립트 답변을 제공하고 싶었습니다.
또한 debugger지시문 중단 점을 추가하여 코드 (크롬 필요)를 통해이 알고리즘의 작동 방식을 확인할 수 있습니다. 개발자 콘솔을 크롬 ( F12Windows 또는 CMD + OPTION + IMac)으로 열고 "코드 스 니펫 실행"을 클릭하십시오. 이것은 @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"
#!/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 쉘 솔루션-총 4 줄 (매개 변수가없는 테스트 없음) :
test $# -eq 1 && echo "$1" && exit
for i in $*; do
$0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done
이것은 자바의 재귀 코드이며 나머지 문자를 추가하는 접두어를 갖는 것이 좋습니다.
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 CAB CBA
완전하기 만하면 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
반응형
'program story' 카테고리의 다른 글
| virtualenv를 복제하는 방법 (0) | 2020.07.25 |
|---|---|
| 40 억 회 반복 Java 루프가 2ms 만 걸리는 이유는 무엇입니까? (0) | 2020.07.25 |
| Pandas의 부울 색인 생성을위한 논리 연산자 (0) | 2020.07.25 |
| ESI 및 EDI 레지스터의 목적은 무엇입니까? (0) | 2020.07.25 |
| "정적"과 "정적 인라인"기능의 차이점은 무엇입니까? (0) | 2020.07.25 |