문자 세트와 레이어 수를 기반으로 비 반복적 인 순열 조합을 생성하고 동일한 조합의 모든 문자를 제외하는 방법은 무엇입니까?

효율적인 문자 배열 및 조합의 생성 : 복제를 피하고 동일하게 제외

이 기사에서는 주어진 문자 세트 및 레이어 수를 기반으로 비 반복적 인 순열 조합을 생성하는 방법을 설명하고 모든 문자가 동일한 위치를 효과적으로 제외합니다. 예를 들어, 문자 세트는 'a'및 'b'이며 다른 층의 조합을 생성합니다. 첫 번째 층은 'a', 'b'; 두 번째 층은 'ab', 'ba'( 'aa', 'bb'제외); 세 번째 층에는 'aab', 'aba', 'abb', 'baa', 'bab', 'bba'등이 포함됩니다.

디지털 교체 방법과 역 추적 방법의 두 가지 알고리즘 전략을 채택합니다.

방법 1 : 디지털 교체 방법 (더 간결한)

이 메소드는 순열을 m 자리 숫자로 취급합니다. 캐릭터 세트 'a', 'b'를 예로 들어, 'a'는 0이고 'b'는 1입니다. 모든 m 자리 숫자를 반복하여 문자 조합으로 변환하십시오. 동일한 조합을 배제하기 위해, 생성 된 M-figit 수가 (11 ... 1)으로 나눌 수 있는지 여부가 결정된다 (1의 수는 층 M의 수와 동일).

파이썬 코드 예 :

 def generate_combinations (charset, layers, allow_all_same = false) :
    결과 = []
    n = 렌 (숯불)
    all_ones = sum (범위 내에서 n ** i (레이어))
    범위 (n ** 층)의 i를 위해 :
        allow_all_same 또는 i % all_ones! = 0 : #exclude combind = ""인 경우
            온도 = i
            _ in range (레이어) :
                조합 = charset [temp % n] 조합
                온도 // = n
            결과. Append (조합)
    반환 결과

print (generate_combinations ( 'ab', 2)) # [ 'ab', 'ba']
print (generate_combinations ( 'ab', 2, true)) # [ 'aa', 'ab', 'ba', 'bb']
print (generate_combinations ( 'ab', 3)) # [ 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
print (generate_combinations ( 'abc', 2)) # [ 'ab', 'ac', 'ba', 'bc', 'ca', 'cb']

방법 2 : 역 추적 방법 (이해하기 쉬운)

Backtrace는 모든 조합을 시도하는 재귀 알고리즘입니다. 각 단계에서 캐릭터를 현재 조합에 추가하고 더 긴 조합을 재귀 적으로 생성합니다. 플래그를 사용하여 현재 조합이 동일한 문자인지 확인하고 복제와 동일한 조합을 피하십시오.

파이썬 코드 예 :

 def generate_combinations_recursive (charset, layers, allow_all_same = false) :
    결과 = []
    current_combination = [ ''] * 레이어

    Def Backtrack (index, all_same) :
        인덱스 == 레이어 인 경우 :
            All_Same이 아닌 경우 :
                results.Append ( "". 가입 (current_combination))
            반품
        숯으로 char :
            current_combination [index] = char
            백트랙

    숯으로 char :
        current_combination [0] = char
        백 트랙 (1, allow_all_same 아님)

    반환 결과


print (generate_combinations_recursive ( 'ab', 2)) # [ 'ab', 'ba']
print (generate_combinations_recursive ( 'ab', 2, true)) # [ 'aa', 'ab', 'ba', 'bb']
print (generate_combinations_recursive ( 'ab', 3)) # [ 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']]]
print (generate_combinations_recursive ( 'abc', 2)) # [ 'ab', 'ac', 'ba', 'bc', 'ca', 'cb']

두 방법 모두 문제를 효과적으로 해결할 수 있으며 선택은 특정 요구와 선호도에 따라 다릅니다. 디지털 교체 방법이 더 간단하고 역 추적 방법을 이해하고 확장하기가 더 쉽습니다.

위 내용은 문자 세트와 레이어 수를 기반으로 비 반복적 인 순열 조합을 생성하고 동일한 조합의 모든 문자를 제외하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!