고정 된 알파벳에서 3 개의 기호로 된 정렬 된 집합의 열거에 대한 무작위 액세스

Question

예를 들어 5 문자의 문자가 있다고 가정합니다. ABCDE.

이제 이러한 문자 3 개를 모두 나열하려고합니다. 각 글자는 한 번만 출품 될 수 있으며, 글자의 순서는 중요하지 않습니다 (따라서 세트의 글자는 정렬되어야합니다).

1. ABC
2. ABD
3. ABE
4. ACD
5. ACE
6. ADE
7. BCD
8. BCE
:

그래서 우리는 다음 세트를 얻을 수 5,

9. BDE
10. CDE
10 개 세트의 총

. 순서는 사전 편집입니다.

알파벳 길이가 N (이 예에서는 5)이고 집합 길이가 M (이 예에서는 3)이라고 가정합시다. 우리는 모든 가능한 경우 수있는 방법, N 및 M을 알고 :

1. 가 최악의 O(M+N)에 조합의 총 수를 말해 (대답이 예에서는 10입니다)?
2. 최악의 경우 주어진 수 (주어진 1, 반환 ABC, 반환 5, 반환 ACE 등)와 함께 조합을 출력 하시겠습니까? O(M+N)?

전체 목록을 생성하여 O(M^N) 복잡도로 작업하는 것이 쉽지만 더 나은 해결책이 있는지 궁금합니다.

Answer 1

첫 번째 질문에 대한 대답은 간단합니다. C(n,r)입니다. 여기서 r 개의 항목을 모두 세트로 선택해야합니다. 수식은 다른 장소 간의 here이다

C(n,r) = n!/(r! (n-r)!) 

조합으로 조합 번호 i 관한 부호화 데에 달려 다른 모든 컴퓨팅 않고 i'th 조합을 선택하는 기능. 즉

(EDIT)

해결책은 파이썬이 보이는 문제 더 생각해 데 ... 훨씬 더 어려운 것 많은 생각이 필요합니다 :

from math import factorial 

def combination(n,r): 
    return factorial(n)/(factorial(r) * factorial(n-r)) 

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 

def showComb(n,r,i,a): 
    if r < 1: 
     return "" 
    rr = r-1 
    nn = max(n-1,rr) 
    lasti = i 
    i -= combination(nn,rr) 
    j = 0 
    while i > 0: 
     j += 1 
     nn = max(nn-1,1) 
     rr = min(rr,nn) # corrected this line in second edit 
     lasti = i 
     i -= combination(nn,rr) 
    return a[j] + showComb(n-j-1,r-1,lasti,a[(j+1):]) 

for i in range(10): 
    print(showComb(5,3,i+1,alphabet)) 

을 ... 질문에 표시된 목록을 출력합니다.

내가 사용한 접근법은 나머지 세트 요소의 조합 수를 사용하여 주어진 숫자의 첫 번째 요소가 어느 것인지 찾아내는 아이디어를 사용하여 i'th 출력 세트의 첫 번째 요소를 찾는 것입니다. i .

즉 C (5,3)의 경우 첫 번째 C (4,2) (= 6) 출력 세트의 첫 문자는 'A'이고 그 다음 C (3,1) (= 3) 출력 세트가 'B'이면 C (1,1) (= 1) 세트의 첫 문자가 'C'입니다.

그런 다음 함수는 나머지 요소를 재귀 적으로 찾습니다. showComb()은 tail-recursive이므로 원하는 경우 루프로 표시 할 수 있지만 재귀 버전은이 경우 이해하기 쉽습니다.

추가 테스트를 들어, 다음의 코드는 유용 할 수있다 :이 경우, 모든 실시 예 120이 올바른지 확인

import itertools 

def showCombIter(n,r,i,a): 
    return ''.join(list(itertools.combinations(a[0:n],r))[i-1]) 

print ("\n") 

# Testing for other cases 
for i in range(120): 
    x = showComb(10,3,i+1,alphabet) 
    y = showCombIter(10,3,i+1,alphabet) 
    print(i+1,"\t",x==y,"\t",x,y) 

....

나는 r 될 것입니다 정확히 시간 복잡도하지만 showComb()에 대한 호출의 수를 계산하지 않은 및 while 루프는 n 배 이하를 실행합니다. 따라서, 질문의 용어에서, 나는 우리가 factorial() 함수가 상수 시간에 계산 될 수 있다고 가정한다면 복잡성은 O (M + N)보다 작을 것이라고 확신합니다. 이것은 나쁜 근사값이라고 생각하지 않습니다. 구현이 순진하지 않는 한.

Answer 2

첫 번째 부분에 동의하면이 방정식을 원하는 언어로 입력하십시오.

x=12 
y=5 
z=1 
base=1 
until [[ $z -gt y ]] 
do 
base=`echo $x $z $base|awk '{print ($1/$2) * $3}'` 
x=`expr $x - 1` 
z=`expr $z + 1` 
echo base:$base 
done 

echo $base 

위의 예는 792 개의 조합으로 5 개 세트로 배열 된 12 개의 항목을 사용합니다.

질문의 두 번째 부분을하려면 ... 나는 단지 그것에 대해 생각하고 있지만 어떤 스트레칭으로도 앞으로 나아갈 수는 없습니다.