반복을 사용한 부분 순열. 모든 솔루션 목록을 나열하십시오 알고리즘

Question

최상의 조언과 조언을 기다리고 있습니다. 나는 다른 상자와 물건에 문제가있다.

설명해 드리겠습니다. 예를 들어 상자 2 개와 개체 3 개가 있습니다. 그래서 저는 2^3 = 8 가능한 해를 가진 모든 해를 계산합니다. 상자 목록 {-1, 0}. 객체 목록 {0, 1, 2}.

하나 개의 솔루션에 대한 나의 표현은

: 배열

1 solution : [-1,-1,-1]; 
2 solution : [0,-1,-1]; 
3 solution : [-1,0,-1]; 
4 solution : [-1,-1,0]; 
5 solution : [0,0,-1]; 
6 solution : [-1,0,0]; 
7 solution : [0,-1,0]; 
8 solution : [0,0,0]; 

지금 내 알고리즘을 제시 [objects.length]이 작동하지 않습니다 :

이

Array box = {-1, 1} 
Array object = {0, 1, 2} 
Array solutions = {} 

// INITIALISATION 
Stack sbox = box; 
Stack sobject = object; 

WHILE sobject not empty DO 
    object = Pop sobject; 

    FOR i from 0 to box.length DO 
      solution[object] = box[i]; 
    FIN POUR 
END WHILE 

그러나이 솔루션이 정확하지 I 때문에 단지 6 가지 솔루션 만 제공합니다.

다른 문서 또는 조언을 통해 저를 도울 수 있습니까? 감사. 객체의

Answer 1

상자 배열이 {-1, 0} 인 이유를 모르겠다. 어쨌든 아래 코드가 작동합니다. 기수 (상자 수) 만 있으면 순열의 총 수를 반복해서 나눕니다. 귀하의 경우, 당신은 2^3 = 8 솔루션을 가지고, 기수는 2이고, 외부 루프에서 0, 1, 2, .. 7을 시도하고 내부 루프에서 기수를 나눕니다. 당신이 상자를 많이있을 때

int[] box = {-1, 0}; 
    int objects = 3; 
    int total = (int) Math.pow(box.length, objects); 
    int radix = box.length; 
    for (int i = 0; i < total; i++) { 
     int v = i; 
     for (int pos = 0; pos < objects; pos++) { 
      System.out.print(box[v % radix] + " "); 
      v = v/radix; 
     } 
     System.out.println(); 
    } 

이 방법을 사용하면 (재귀 또한 스택을 필요로) 큰 스택을 피할 수 있습니다. 더 복잡한 경우에, 당신은 여러 radices, e, g를 가질 수 있습니다. 첫 번째 상자의 경우 항목 A와 B가 허용되고 두 번째 상자의 경우 B, C와 D가 허용됩니다.

Answer 2

숫자 0 당신의 상자 줘

... N

번호 : 단순히 기본 n으로 숫자를 세고있는 각을 넣어 상자 결정 결과의 숫자를 사용할 수 있습니다보다 m

목적. 모든 조합을 얻으려면 0에서 m^n-1까지 계산하십시오. 상자 3의

예 번호, 오브젝트 4

0000 all in boy 0 
0001 fist three in box 0 last one in box 1 
0002 
0010 
0011 
0012 
0020 fist two in box 0, third one in box 2 and last one in box 0 
... 
2210 fist two in box 2, third one in box 1 and last one in box 0 
2211 
2212 
2220 
2221 
2222 

모든 m^n 가능한 조합을 얻을이 방법의 수.

Answer 3

가장 간단한 해결책은 아마도 재귀 함수 일 것입니다.

기본적으로 각 색인 (개체)에 대해 가능한 모든 요소 (상자)를 시도한 다음 다음 색인으로 다시 반복합니다.

box = {-1, 0} 
objectCount = 3 
solutions = {} 

getPermutations(0, new array[objectCount]) // function call 

getPermutations(index, output) 
    if index == output.length 
     solutions.add(output) 
    else 
     for each box b 
     output[index] = b 
     getPermutations(index + 1, output) 

Live Java demo.