리스트를 사용하지 않고 이진 트리를 허용하기

이진 트리의 모든 가능한 순열을 생성하기위한 알고리즘을 찾고 목록을 사용하지 않고이를 수행해야합니다 (트리 자체는있을 수없는 의미와 제한을 가지고 있기 때문입니다. 목록으로 번역). 나는 높이가 3 이하인 나무에서 작동하는 알고리즘을 발견했지만, 높이가 올라갈 때마다 높이 당 가능한 순열 세트가 하나씩 느슨해졌습니다.리스트를 사용하지 않고 이진 트리를 허용하기

각 노드는 원래 상태에 대한 정보를 전달하므로 한 노드가 가능한 모든 순열이 해당 노드에 대해 시도되었는지 확인할 수 있습니다. 또한, 노드는 날씨에 대한 정보를 전달하거나 '스왑 된'것이 아니라, 즉 가능한 모든 순열을 볼 수있는 경우 서브 트리입니다. 트리는 왼쪽 중심에 놓여 있습니다. 즉, 오른쪽 노드는 항상 (이 알고리즘에 대해 커버 할 필요가없는 경우를 제외하고는) 리프 노드이고, 왼쪽 노드는 항상 리프 또는 분기 중 하나 여야합니다.

내가 지금 사용하고 알고리즘은 다음과 같은 종류의 설명 될 수 있습니다 : 등등

  branch 
      / | 
     branch  3 
     / | 
    branch 2 
/ | 
    0  1 


      branch 
      / | 
     branch  3 
     / | 
    branch 2   
/ | 
    1  0   <-- first swap 



      branch 
      / | 
     branch  3 
     / | 
    branch 1   <-- second swap 
/ | 
    2  0 



      branch 
      / | 
     branch  3 
     / | 
    branch 1   
/ | 
    0  2 <-- third swap 


      branch 
      / | 
     branch  3 
     / | 
    branch 0 <-- fourth swap   
/ | 
    1  2

과 :

는

if the left child node has been swapped 
     swap my right node with the left child nodes right node 
     set the left child node as 'unswapped' 
    if the current node is back to its original state 
     swap my right node with the lowest left nodes' right node 
     swap the lowest left nodes two childnodes 
     set my left node as 'unswapped' 
     set my left chilnode to use this as it's original state 
     set this node as swapped 
     return null 
    return this; 
else if the left child has not been swapped 
    if the result of trying to permute left child is null 
    return the permutation of this node 
    else 
    return the permutation of the left child node 
if this node has a left node and a right node that are both leaves 
    swap them 
    set this node to be 'swapped'

알고리즘으로의 원하는 동작은 다음과 같이 될 것이다 ...

출처

2009-03-26 Mia Clarke

냄새는 숙제와 비슷하지만 실제 노력을 기울인 것처럼 보입니다. 그렇기 때문에 숙제 스타일의 일반적인 질문보다 훨씬 좋습니다. 그럼에도 불구하고, 그 데이터 구조는 숙제에도 불구하고 퍼뮤팅 (permuting)을 위해 매우 열악합니다. – Welbog

나는 그것이 숙제가 아니기 때문에 두려워한다. (나는 그랬 으면 좋겠다.) 나는이 직업에 대한 실제 직업을 가지고있다. ;;) –

Oh 와우. 이건 정말 짜증나. 왜냐하면 이것은 미친 문제 같아. 내가 무엇을 생각해 낼지 알게 될거야. – Welbog

이 구조는 순열에 완전히 부적합하지만 왼쪽 중심이라는 것을 알고 있기 때문에 도움이되는 몇 가지 가정을 할 수 있습니다.

나는 당신과 비슷한 방식으로 작업을 시도했는데, 충분하지 않은 정보 (스왑되거나 그렇지 않은) 만 가지고 있다는 사실에 항상 빠져 들었다. 4 개의 잎을 위해, 당신은 4를 가지고있다! (24) 가능한 조합이지만, 스왑 된 상태 정보를 저장하기 위해 실제로는 3 개의 분기 (3 비트, 8 개의 가능한 조합) 만 있습니다. 당신은 단순히이 정보를 저장할 장소가 없습니다.

하지만 트리를 통과하는 잎사귀를 작성하고 잎의 수를 사용하여 필요한 스왑의 수를 결정한 다음 트리를 나무에 남기지 않고 체계적으로 스왑을 통과 할 수 있습니다. 응용 프로그램에 적합하지 않을 수 있습니다

For each permutation 
    Encode the permutation as a series of swaps from the original 
    Run these swaps on the original tree 
    Do whatever processing is needed on the swapped tree

같은

이

뭔가,하지만 당신은 부여하지 않은 당신이 그것을 당신이 그것을하고있는 방법을해야 할 이유에 대해 많은 세부 사항. 계승 (순열의 수)이 기하 급수적으로 (당신이 가진 "스왑 된"비트의 수)보다 빠르게 증가하기 때문에 당신이 지금하고있는 방식은 간단히 작동하지 않을 것입니다. 8 개의 잎이 있다면 7 개의 가지와 8 개의 잎이 총 15 비트가됩니다. 8 잎의 40320 순열과 15 비트의 32768 가능한 조합 만 있습니다. 수학적으로, 순열을 나타낼 수는 없습니다.

출처

2009-03-26 13:42:25 Welbog

아, 당신 말이 맞아요, 나는 그것에 대해 생각하지 않았습니다. 고맙습니다. 대단히, 나는 당신의 제안 된 방법을 시도하고 그것이 작동하는지 확인합니다. 나는 당신의 대답에 대한 충분한 평판 점수를 얻지 못했지만, 만약 내가 가진다면, 나는 이것을 바지 바깥으로 끌어 올 것입니다. 다시 한 번 감사드립니다! –

나는 그 점에 대해서 Banang이 아니다. 흥미로운 문제를 가져 주셔서 감사합니다. 내 솔루션이 당신을 위해 일하기를 바랍니다. 그렇지 않다면 다른 의견으로 알려주십시오. 우리는 우리가 생각해 낼 수있는 것을 보게 될 것입니다. – Welbog

트리에있는 모든 항목의 목록을 만드는 데 문제가 있습니까? 생성 가능한 수단을 사용하여 가능한 모든 주문을 작성한 다음 (Knuth 4 권 참조) 트리 구조에 다시 매핑하십시오.

출처

2009-03-26 13:34:35 HUAGHAGUAH

리스트를 사용하지 않고 이진 트리를 허용하기

답변

관련 문제