n 개의 요소를 k 범주로 나열하는 순서

Question

특정 시간 {t1, ..., tk}에 발생하는 n 개의 이벤트 {v1, ..., vn}이 있습니다. 여기서 k는 < = n 동시에), 나는 이것이 발생할 수있는 각 방법을 열거해야한다. 우리는이 사건이 있다면

예를 들어, 내가 할 수 :

{v1을 < V2}, {v2를 < (V1)} (2 회)

{V1 = V2} (1 시간)

우리는 3 사건이 있다면, 나는 3 별개의 시간이 모두 6 개 순서 부를 가질 수

플러스

{V1 = V2 < V3}, {V1 = V3 < V2}, {V2 = V3 < V1}, { v1 < v2 = v3}, {v2V1 = V3}, {V3 < V1 = V2} (2 회)

{V1 = V2 = V3} (1 시간)

그래서 실제로 가능한 모든 그룹을 원하지 않기 때문에 {V1 = v2 < v3}은 예를 들어 {v2 = v1 < v3}과 같습니다.

제 생각에는 k = n 어쨌든 할 사건이있는 경우 n 이벤트의 모든 순열을 생성해야하는데,이 방법은 제가 수행 할 수있는 방법입니다. 그래서 아마도 위에 가능한 범주를 생성 할 수 있습니다. 그런 다음 복제본을 잘라내는데, 예를 들어 {v3 = v4 = v2 < v1 = v6 < v5}가 이전에 효율적으로 수락 한 복제본인지 확인하는 방법을 모르겠습니다.

아마도 순열 목록에서 작동 할 때 더 체계적 일 수 있으며 지금까지 보관 한 목록을 다시 확인하지 않고 중복 된 데이터를 삭제하는 방법을 파악할 수 있습니까?

적당히 많은 수의 이벤트에 대해서는 적절한 시간 내에 작동하지 않지만 가능한 한 높게 설정하고 싶습니다. 6은 괜찮을 것이며, 8 또는 10은 더 좋습니다.

저는 MATLAB을 사용하고 있습니다 만, 나는 누군가가 그런 문제에 대해 최적이라고 제안 할 수있는 언어를 추구하고자하며 일반적인 언어 불가지론에 관한 조언은 매우 환영하고 감사합니다.

가 표준 알고리즘 (! N있다 순열, 분명히)를 사용하여 v1…vn의 순열을 생성합니다

Answer 1

여기에 한 가지 방법 (코드는 다음)입니다.

vp1 R1 vp2 R2 vp3 … Rn-1 vpn

어디 Ri 항상 < 될 수 있으며, pi < pi+1 경우 = 수 있습니다 : 각 순열의 경우 vp1…vpn 가능한 모든 수식을 열거.

예를 들어, n은 3 인 경우

v1 v2 v3: v1 < v2 < v3; v1 < v2 = v3; v1 = v2 < v3; v1 = v2 = v3 
v1 v3 v2: v1 < v3 < v2; v1 = v3 < v2 
v2 v1 v3: v2 < v1 < v3; v2 < v1 = v3 
v2 v3 v1: v2 < v3 < v1; v2 = v3 < v1 
v3 v1 v2: v3 < v1 < v2; v3 < v1 = v2 
v3 v2 v1: v3 < v2 < v1 

당신은 재귀 적 관계를 열거 할 수 있습니다 (I 손으로, 위의 그것을 어떻게 효율적이었다).

편집 : 슬론 시퀀스 A000670입니다.이 링크에는 다양한 유용한 참조 정보가 들어 있습니다. n = 9 인 경우, 카운트는 7087261로 현저히 실용적입니다. n = 10 인 경우 102247563이며 현대 데스크톱 계산 범위 내에 쉽게 포함됩니다. (나는 matlab에 대해 모르지만). 당신은 단지 그들을 생성하기 위해 찾고 있다면

def rels(perm): 
    if len(perm) == 1: 
    yield perm 
    else: 
    for p in rels(perm[1:]): 
     yield (perm[0], '<') + p 
     if perm[0] < perm[1]: 
     yield (perm[0], '=') + p 

def orders(n): 
    return reduce(lambda a,b:a+b, 
       [[i for i in rels(p)] for p in itertools.permutations(range(n))]) 

>>> print '\n'.join(map(repr,[o for o in orders(4)])) 
(0, '<', 1, '<', 2, '<', 3) 
(0, '=', 1, '<', 2, '<', 3) 
(0, '<', 1, '=', 2, '<', 3) 
(0, '=', 1, '=', 2, '<', 3) 
(0, '<', 1, '<', 2, '=', 3) 
(0, '=', 1, '<', 2, '=', 3) 
(0, '<', 1, '=', 2, '=', 3) 
(0, '=', 1, '=', 2, '=', 3) 
(0, '<', 1, '<', 3, '<', 2) 
(0, '=', 1, '<', 3, '<', 2) 
(0, '<', 1, '=', 3, '<', 2) 
(0, '=', 1, '=', 3, '<', 2) 
(0, '<', 2, '<', 1, '<', 3) 
(0, '=', 2, '<', 1, '<', 3) 
(0, '<', 2, '<', 1, '=', 3) 
(0, '=', 2, '<', 1, '=', 3) 
(0, '<', 2, '<', 3, '<', 1) 
(0, '=', 2, '<', 3, '<', 1) 
(0, '<', 2, '=', 3, '<', 1) 
(0, '=', 2, '=', 3, '<', 1) 
(0, '<', 3, '<', 1, '<', 2) 
(0, '=', 3, '<', 1, '<', 2) 
(0, '<', 3, '<', 1, '=', 2) 
(0, '=', 3, '<', 1, '=', 2) 
(0, '<', 3, '<', 2, '<', 1) 
(0, '=', 3, '<', 2, '<', 1) 
(1, '<', 0, '<', 2, '<', 3) 
(1, '<', 0, '=', 2, '<', 3) 
(1, '<', 0, '<', 2, '=', 3) 
(1, '<', 0, '=', 2, '=', 3) 
(1, '<', 0, '<', 3, '<', 2) 
(1, '<', 0, '=', 3, '<', 2) 
(1, '<', 2, '<', 0, '<', 3) 
(1, '=', 2, '<', 0, '<', 3) 
(1, '<', 2, '<', 0, '=', 3) 
(1, '=', 2, '<', 0, '=', 3) 
(1, '<', 2, '<', 3, '<', 0) 
(1, '=', 2, '<', 3, '<', 0) 
(1, '<', 2, '=', 3, '<', 0) 
(1, '=', 2, '=', 3, '<', 0) 
(1, '<', 3, '<', 0, '<', 2) 
(1, '=', 3, '<', 0, '<', 2) 
(1, '<', 3, '<', 0, '=', 2) 
(1, '=', 3, '<', 0, '=', 2) 
(1, '<', 3, '<', 2, '<', 0) 
(1, '=', 3, '<', 2, '<', 0) 
(2, '<', 0, '<', 1, '<', 3) 
(2, '<', 0, '=', 1, '<', 3) 
(2, '<', 0, '<', 1, '=', 3) 
(2, '<', 0, '=', 1, '=', 3) 
(2, '<', 0, '<', 3, '<', 1) 
(2, '<', 0, '=', 3, '<', 1) 
(2, '<', 1, '<', 0, '<', 3) 
(2, '<', 1, '<', 0, '=', 3) 
(2, '<', 1, '<', 3, '<', 0) 
(2, '<', 1, '=', 3, '<', 0) 
(2, '<', 3, '<', 0, '<', 1) 
(2, '=', 3, '<', 0, '<', 1) 
(2, '<', 3, '<', 0, '=', 1) 
(2, '=', 3, '<', 0, '=', 1) 
(2, '<', 3, '<', 1, '<', 0) 
(2, '=', 3, '<', 1, '<', 0) 
(3, '<', 0, '<', 1, '<', 2) 
(3, '<', 0, '=', 1, '<', 2) 
(3, '<', 0, '<', 1, '=', 2) 
(3, '<', 0, '=', 1, '=', 2) 
(3, '<', 0, '<', 2, '<', 1) 
(3, '<', 0, '=', 2, '<', 1) 
(3, '<', 1, '<', 0, '<', 2) 
(3, '<', 1, '<', 0, '=', 2) 
(3, '<', 1, '<', 2, '<', 0) 
(3, '<', 1, '=', 2, '<', 0) 
(3, '<', 2, '<', 0, '<', 1) 
(3, '<', 2, '<', 0, '=', 1) 
(3, '<', 2, '<', 1, '<', 0)