가변 길이의 가변 개수의 배열에서 1 개의 요소로 구성된 모든 순열을 찾을 수 있습니까?

Question

배열 길이가 다른 D 배열 U입니다. 각 집합에서 1 요소로 구성된 다른 순열을 선택하는 배열 인덱스의 모든 순열을 반환 할 수 있어야합니다. 또한이 알고리즘은 마지막 순열을 기억하는 객체로 표현되고 get_next 메소드로 다음 순열을 반환해야합니다.

예 : U = [array_of_size_n1, array_of_size_n2, array_of_size_n3]n1*n2*n3 순열이 있으며, 각각 요소가 있습니다.

편집 : 수는 또한 다양합니다.

Answer 1

,이 표준 라이브러리의 일부입니다. 그러나 당신이 아니라고 가정 할 때, 의사 코드 버전이 있습니다.

// Create an initialised array of indexes. 
int[] index0(arrays) { 
    // We require all arrays to be non-empty. 
    for a in arrays { 
     assert len(a) != 0; 
    } 
    return new int[len(arrays)]; 
} 

// Increment the indices. Returns false when the indices wrap round to the start. 
bool next_index(indices, arrays) { 
    for (i = len(indices) - 1; i >= 0; --i) { 
     indices[i] += 1 
     if indices[i] < len(arrays[i]) { 
      return true; 
     } 
     indices[i] = 0; 
    } 
    return false; 
} 

이렇게하면 사용할 수 있습니다 (배열이 비어 있지 않은 것으로 가정). 이 예제는 배열의 모든 요소 조합을 출력합니다.

indices = index0(arrays); 
{ 
    for (i = 0; i < len(arrays); ++i) { 
     print arrays[i][indices[i]]; 
    } 
    print 
} while next_index(indices); 

Answer 2

그래서 ... 은이 아닙니다.

반복자가 필요합니다. 마지막 배열을 반복 할 수 있습니다. 해당 배열의 끝 부분에 도달하면 두 번째 마지막 배열에서 현재 위치를 증가시키고 마지막 배열의 시작 부분으로 돌아갑니다.

C 번호의 yield return 구문을 사용하여 psuedocode :

foreach n1 in a1 
    foreach n2 in a2 
     foreach n3 in a3 
      yield return (n1, n2, n3) 

이 편집 : 세트의 수는 다릅니다 경우 재귀 형태 사용할 수 있습니다 동작을 고려

function next(list) 
    firstArray = list.first 
    iterator = iterator(list.rest) 
    if !iterator 
     foreach i in firstArray 
      yield return i 
    else 
     foreach i in firstArray 
      while (iterator.hasNext) 
       yield return (i, iterator.next) 

을 때의 목록 길이 1을 전달한 다음 길이 2의 목록에 대한 동작을 고려하고 실제로 작동한다는 것을 스스로 만족시킵니다.

Answer 3

각 배열의 개별 위치에 대한 카운터를 유지할 수 있습니다. 귀하의 get_next 메서드에서 하나의 카운터를 늘리고 배열의 길이만큼 mod하십시오. 그런 다음 이전 카운터가 0으로 롤오버 할 때마다 다음 카운터를 증가시킵니다.

if (pos3 == array_of_size_n3 -1) 
{ 
    if (pos2 == size_of_array_2 -1) 
    { 
     pos1 = (pos1 + 1) % size_of_array_1 

    } 
    pos2 = (pos2 + 1) % size_of_array_2 
} 
pos3 = (pos3 + 1) % size_of_array_3 

print array1[pos1], array2[pos2], array3[pos3] 

편집 : 배열의 수가 다른 경우 배열의 위치 변수를 유지하십시오. 사실 그게 어쨌든 더 나을거야. 배열 자체를 참조하는 것과 같은 방법으로 pos 변수를 참조 할 수 있습니다.

Answer 4

Anon이 말한 것에 착수하기 위해, 당신은 단지 그것들을 반복하지 않습니다. 각 배열에 대해 마지막 색인이 무엇인지 알 수 있도록 수업에서 상태를 유지 관리합니다. 논리는 동일하지만 연속 루프에서는 실행되지 않습니다. 의사 코드 로직은 다음과 같습니다 itertools.product : 당신이 파이썬을 사용하는 경우

 
get_next() 
{ 
    oldn3 = this.n3; 
    oldn2 = this.n2; 
    oldn1 = this.n1; 

    if(this.n3 == this.a3.Count) 
    this.n3 = 0; 
    else 
    this.n3++; 

    if(oldn3 > this.n3) 
    if(this.n2 == this.a2.Count) 
     this.n2 = 0; 
    else 
     this.n2++; 

    if(oldn2 > this.n2) 
    if(this.n1 == this.a1.Count) 
     this.n1 = 0; 
    else 
     this.n1++; 

    if(oldn1 > this.n1) 
    return NO_MORE_PERMS; 

    return [n1,n2,n3]; 
} 

getCurrent() 
{ 
    return [n1,n2,n3]; 
}