요소가 제자리에 유지되지 않은 순열을 찾으십시오

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

  •  06-07-2019
  •  | 
  •  

문제

각 요소가 원래 위치와 다른 순열로 작업하고 있습니다. 주어진 {입력 길이, 행 및 숫자}가 출력 번호를 제공하는 알고리즘을 원합니다. 예는 다음과 같습니다.

입력 길이가 4 인 경우 0123의 모든 순열은 다음과 같습니다.

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

숫자가없는 순열은 같은 장소에 있습니다 (모든 숫자가 이동했습니다).

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

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

입력이 {4,1,1} 인 경우 출력은 1230의 두 번째 숫자 (2)입니다.

행 번호는 순열의 누베르보다 클 수 있습니다. 이 경우, 나머지 모듈로는 순열 수를 가져옵니다 (위의 경우, modulo 9).

C 언어에서는 좋을 것입니다.

(숙제가 아닙니다. 일을위한 것입니다. Cuckoo Hashing이 알아야 할 경우. 테이블 수가 2보다 큰 경우 BFS보다 더 나은지 확인하기 위해 각 단계에서 제시 할 스왑을 무작위로 선택하고 싶습니다. .))

도움이 되었습니까?

해결책

Python의 Brute-Force 접근 방식 (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()

다른 팁

왜 나무를 만들고 반복하지 않습니까?

예를 들어, 숫자가있는 경우 0123, 당신은 왼쪽 대부분의 숫자가 set {1,2,3}. 이것은 나무에서 첫 번째 레벨 역할을합니다.

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

이 접근법에서 조심해야 할 것은 3이 유일한 옵션 인 지점의 끝에 도착하면 삭제하는 것입니다.

을 위한 n > 10 모든 순열을 생성 한 다음 필터링이 문제가 될 수 있습니다. 나는 나무를 건설하면 이것을 크게 다듬을 것이라고 생각합니다.

필요한 경우 나무를 즉석에 만들 수 있습니다. 순서는 나무를 가로 지르는 방식으로 정의 할 수 있습니다.

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