가변 중첩 루프를 구조화하는 좋은 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/659117

문제

가변 길이 배열이있는 언어로 작업한다고 가정합니다 (예 : A[i] 모든 i 안에 1..A.length) 그리고 취하는 루틴을 작성해야합니다 n (n : 1..8) 가변 길이의 가변 길이는 길이의 가변 길이 배열로 된 항목의 배열 n, 가능한 모든 길이의 절차를 호출해야합니다. n 첫 번째 배열에서 첫 번째 배열에서 선택되는 항목, 두 번째 배열은 두 번째 배열에서 선택됩니다.

구체적인 무언가를 시각화하려면 일상적인 데이터를 가져와야한다고 상상해보십시오.

[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]

다음 절차 호출 (어떤 순서로도) :

try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
 :
try_on ['derby','bolo',...'slippers']

이것은 때때로 중국 메뉴 문제라고하며 고정 된 n 아주 간단하게 코딩 할 수 있습니다 (예 : n = 3, 의사 코드)

procedure register_combination( items : array [1..3] of vararray of An_item)
    for each i1 from items[1]
        for each i2 from items[2]
            for each i3 from items[3]
                register( [ii,i2,i3] )

그러나 만약 그렇다면 n 다음과 같은 서명을 제공 할 수 있습니다.

procedure register_combination( items : vararray of vararray of An_item)

작성된 코드에는 추악한 사례 명세서가 포함되어 있으며,이 문서는 훨씬 간단한 솔루션으로 대체되었습니다. 그러나 나는 그것이 이것이 최선인지 확실하지 않습니다 (그리고 그것은 확실히 유일한 것은 아닙니다) 이것을 리팩터링하는 방법입니다.

어떻게 하시겠습니까? 영리하고 놀라운 것은 좋지만 명확하고 관리 가능한 것이 더 좋습니다. 저는이 코드를 통과하고 있으며 다시 전화를 받고 싶지 않습니다. 간결하고 명확합니다 그리고 영리한 것이 이상적입니다.

편집 : 오늘 나중에 다른 사람들이 응답 할 기회를 얻은 후에 솔루션을 게시하겠습니다.

티저 : 재귀 솔루션을 판매하려고했지만 그들은 가지 않기 때문에 HLL에서 Fortran을 쓰는 것을 고수해야했습니다.

내가 함께한 답변은 아래에 게시되었습니다.

도움이 되었습니까?

해결책 3

그들이 재귀에 반대했기 때문에 (묻지 말고) 나는 지저분한 사례 진술에 반대했다. 버그) 나는 이것과 함께 갔다 :

procedure register_combination( items : vararray of vararray of An_item)
    possible_combinations = 1
    for each item_list in items
        possible_combinations = possible_combinations * item_list.length
    for i from 0 to possible_combinations-1
        index = i
        this_combination = []
        for each item_list in items
            item_from_this_list = index mod item_list.length
            this_combination << item_list[item_from_this_list]
            index = index div item_list.length
        register_combination(this_combination)

기본적으로, 나는 얼마나 많은 조합이 있는지, 각각의 조합을 할당 한 다음 해당 조합을 생성하는 숫자를 통해 루프합니다. 새로운 속임수가 아니라 나는 의심 스럽다.

더 짧고 목록 길이의 실질적인 조합에 대해 작동합니다 (2^60 이상의 조합이있는 경우 다른 문제가있는 경우), 재귀가 아니며 버그.

다른 팁

재귀 알고리즘 중 하나입니다

procedure register_combination( items )
        register_combination2( [], items [1:] )

procedure register_combination2( head, items)
    if items == []
        print head
    else
       for i in items[0]
           register_combination2( head ++ i, items [1:] )

또는 테일 호출과 동일하게 최적화, 인덱스의 배열을 사용하고 해당 배열의 길이에 도달 할 때까지 마지막 인덱스를 증가시킨 다음 증가를 전달합니다.

재귀.

또는 더 나은 것은 스택과 같은 구조와 진술을 사용하여 재귀를 제거하려고 노력합니다.

당신의 문제에 대해 당신은 (변수 인수가있는 함수를 호출) 전적으로 코딩하는 프로그래밍 언어에 달려 있습니다. 그들 중 많은 사람들이 변수 인수를 전달할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top