요소가없는 곳에 순열 찾기

Question

각 요소가 원래 위치와 다른 순열로 작업하고 있습니다. 알고리즘 {input length, row and digit}이 주어진다면 출력 번호를 줄 것입니다.

0123,0132,0213,0231,0312,0321, 
1023,1032,1203,1230,1302,1320, 
2013,2031,2103,2130,2301,2310, 
3012,3021,3102,3120,3201,3210 

어떤 숫자가 같은 장소에없는되는 순열 (모든 숫자는 이동) : 다음의 예이다 : 입력 길이 네 경우

는 0123의 모든 순열은

번호 매기기는 0에서 시작하므로 함수에 대한 입력이 {4,0,0}이면 출력은 0 번째 (첫 번째) 순열의 0 번째 (가장 왼쪽) 자릿수 여야합니다. 1032 첫 번째 숫자는 입력 {4,1,1} 인 경우, 출력은 2

은 행의 수가 클 수 이하가 될 수있다 1230 번째 숫자, 1.

이다

순열. 이 경우 나머지를 순열의 수를 모듈로 취합니다 (위의 경우에는 모듈로 9).

C 언어는 훌륭합니다.

(숙제가 아닙니다. 알고 있어야하는 경우 숙제가 아닙니다. 각 단계에서 스왑을 무작위로 선택하여 BFS보다 더 좋을지 확인하고 싶습니다. .이보다 큰) 파이썬에서

Answer 1

브 루트 포스 접근 방식은 (는) 당신의 C 구현을 테스트하는 데 사용할 수 있습니다

#!/usr/bin/env python 
from itertools import ifilter, islice, permutations 

def f(length, row, digit): 
    """ 
    >>> f(4, 0, 0) 
    1 
    >>> f(4, 1, 1) 
    2 
    """ 
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..) 
    # 2. filter out permutations that have digits inplace 
    # 3. get n-th permutation (n -> row) 
    # 4. get n-th digit of the permutation (n -> digit) 
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit] 

def not_inplace(indexes): 
    """Return True if all indexes are not on their places. 

    """ 
    return all(i != d for i, d in enumerate(indexes)) 

def nth(iterable, n, default=None): 
    """Return the nth item or a default value. 

    http://docs.python.org/library/itertools.html#recipes 
    """ 
    return next(islice(iterable, n, None), default) 

if __name__=="__main__": 
    import doctest; doctest.testmod() 

Answer 2

왜 그냥 나무를 구축하고 그것을 통해 반복?

예를 들어 숫자가 0123 인 경우 가장 왼쪽 숫자가 set {1,2,3} 일 수 있음을 알 수 있습니다. 이것은 당신의 나무에서 당신의 첫 번째 레벨의 역할을합니다.

그런 다음 1로 시작하는 경로를 내려 가면 {0, 2, 3}의 세 가지 옵션 만 사용할 수 있습니다. 첫 번째 레벨에서 2로 시작하는 경로를 내려가 보면 두 번째 옵션 인 {0,3} 만 있습니다. 왼쪽에서 두 번째 숫자에 1을 사용할 수없고 2가 이미 사용되었으므로 (목록에서 2를 팝 할 수 있기 때문입니다

이 접근법에서주의해야 할 점은 3이 유일한 옵션 인 분기의 끝에 도달하는 경우입니다.이 경우 3 분기를 삭제하면됩니다.

n > 10의 경우 모든 순열을 생성하고 필터링이 문제가 될 수 있습니다. 나는 나무를 쌓아 두는 것이이 부분을 상당히 다듬을 것이라고 생각합니다.

필요한 경우 즉시 트리를 작성할 수 있습니다. 당신의 주문은 당신이 나무를 가로 지르는 방법에 의해 정의 될 수 있습니다.