반복되는 값이없는 k-ary 트리를 만듭니다.

Question

x1 및 x2의 두 값이 있다고 가정합니다.

단일 루트가 주어지면 k-ary 트리를 사용하여 x1과 x2의 모든 조합을 만드는 방법은 무엇입니까?

예 : 레벨 #1에서

#0 root 
    / \ 
#1 x1  x2 
    | 
#2 x2 

내가 초기 요소 x1 및 x2 있습니다.

레벨 #2에서 나는 조합 x1x2을, x2을 가지고 있지만 그것은 가 조합 반복 될 것이기 때문에 x1이없는 (요소가 여기에 주문에 대해 x2x1을, 우리는 상관하지 않습니다).

내가 두 개 이상의 요소를 가지고 있다면 레벨이 요소의 수에서 1을 뺀

이미 초기 #1 수준을 구축 동일 할 때까지 나무에 계속 것입니다. 반복 조합을 사용하지 않고 트리를 계속 생성하려면 어떻게해야합니까? 다시 말해, 을 확인하는 방법은 주어진 요소를 트리에 배치해야합니다. 가장 효과적인 방법입니다. 거기에 몇 가지 잘 알려진 알고리즘이 무엇입니까?

추가 정보 : PHP

Answer 1

편집 : 트리

내 생각은 n 개의 요소 (x1, x2,... ,xn)에 대한 n 차 트리를 가지고있다 구축에 일부 수정. 루트가 x0 일 때 어떤 노드라도 xi(0 <= i <= n)이면 모든 자식을 가지고 있어야합니다. xj 여기서 (i < j <= n)입니다. 이 방법으로 모든 반복되지 않는 조합을 가질 수 있습니다. 예 : n = 3 인 경우 3 진 트리는 다음과 같습니다.

root ---> x1 ---> x2 ---> x3 
      | ---> x3 
root ---> x2 ---> x3 
root ---> x3