정확히 하나의 항목으로 공통적으로 목록을 생성하십시오.

Question

파이썬에서는 아이디어를 짚어보고 있지만 올바르게 구현하는 방법을 정확히 모르겠습니다.

저는 26 자 ('A'- 'Z')의 풀을 가지고 있으며, 각 글자는 필요한만큼 사용할 수 있습니다. 이 편지들을 사용하여 목록을 만들고 싶습니다. 각 목록은 그 안에 반복이없는 10 자 길이가 될 것이고 나는 생성 된 두 목록을 비교하면 정확히 하나의 문자가 있음을 보장하고자합니다.

질문 :

• (즉, 라이브러리 함수를 사용하여)이 작업을 수행 할 수있는 간단한 방법이 있나요?
• 풀의 크기 (pool_size)와 목록의 길이 (list_length)를 고려하여 만들 수있는 최대 목록 수를 계산할 수 있습니까?

관련 자료에 대한 모든 의견을 환영합니다. 나는 나의 Archimedean lever를 배치하기위한 어딘가의 구현이 필요하지 않습니다. (아이디어를 만들기 전에 기초가 필요합니다).

"나에게 설 수있는 곳을주세요. 나는 땅을 움직일 것입니다." - 아르키메데스

업데이트 : 알파벳이 작동하기에 충분했다고 생각하는 것이 얼마나 순진한 지 알 수 있습니다. 풀을 300 개의 심볼로 확장하되 목록을 길이 10으로 유지합시다. 작동합니까?

Answer 1

선택할 수있는 글자가 26 개인 경우 두 개의 목록 만 생성 할 수 있습니다.

임의로 한 글자를 선택하고 두 목록에 모두 넣으십시오. 그런 다음 18 개의 다른 글자를 골라 각 목록에 임의로 9 개를 씁니다. 당신은 단지 일곱되지 않는 문자가 있기 때문에 제약 조건을 만족하는 것은 불가능 세 번째 목록을 추가하는 경우

ABCDEFGHIJ 
AKLMNOPQRS 

: 그런 다음 목록은 다음과 같이 보일 것입니다. 세 번째 목록은 다른 목록 중 하나와 적어도 두 글자를 공유해야하며, 허용하지 않습니다.

---

업데이트

이 부분적으로 업데이트 된 질문에 대한 대답하지만 최적의 해결책을 찾기 위해 당신이나 다른 사람을 도움이 될 나는 어쨌든 그것을 게시 할 수 있습니다. n 기호와 쉽게 (1 편지를 따기 모든 목록에 추가 위에서 설명한 알고리즘을 사용하여 적어도 floor((n-1)/(x-1)) 목록을 생성 할 수 있습니다 x 길이의 목록과 일반적으로

. (300 개) 기호와 길이 10의 목록에 대한 그래서 33 목록을 제공합니다.

그러나 다른 알고리즘을 사용하여이 문제를 개선 할 수 있습니다.예를 들어 N은 10이고, X는 전술 한 알고리즘은 단지 세리스트 범 4 인 경우

ABCD 
AEFG 
AHIJ 

그러나 오 개리스트 생산할 수보다 효율적으로 문자를 재사용 알고리즘 :

ABCD 
AEFG 
BEHI 
CFHJ 
DGIJ 

제가 사용하여 이러한리스트 생성을 욕심 많은 알고리즘 : 각 새 목록에 대해 이전 목록과 가능한 많은 다른 문자를 재사용하십시오. 즉 가능한 한 적은 새 문자를 추가합니다.

두 번째 목록은 첫 번째 목록의 한 문자를 다시 사용하고 세 개의 새 문자를 추가합니다. 세 번째 목록은 처음 두 목록의 다른 문자를 재사용하므로 두 개의 새 문자 만 소개합니다. 네 번째 목록은 이전에 발생한 세 개의 문자를 다시 사용하고 하나 더 새로운 문자를 추가합니다. 이제 최종 목록에서 이전 목록의 각 문자를 다시 사용할 수 있으며 새 문자를 추가 할 필요가 없습니다.

---

업데이트 2

욕심 알고리즘은 확실히 최적의 솔루션이 아닙니다.

하자 시도 : N = 26, X = 2

간단한 솔루션이 최적 25 개 목록 제공 :

AB 
AC 
BC 

:

가

AB 
AC 
AD 
.. 
AZ 

욕심 알고리즘이 있지만 단지 3 개의리스트를 생성을 이제는 규칙 중 하나를 위반하지 않고 더 이상 목록을 추가하는 것은 불가능합니다.

Answer 2

이것은 Set과 Line Length의 모든 값에서 발견 된 일반적인 해결책이었습니다. 첫 번째는 동일한 공통 요소를 공유하는 두 가지 솔루션을 원하지 않지만 각 솔루션이 다른 모든 솔루션과 공통된 요소를 갖기를 원한다고 가정합니다. 양식을 선택하는 데 무한한 풀이 주어지면 총 솔루션 수는 각 솔루션의 길이에 따라 제한됩니다.

예를 들어

SET_LENGTH = 10 
CHOICE_LENGTH = 300 

data = set(range(CHOICE_LENGTH)) 
solutions =[] 
solution_sets = [] 
used = set() 

while True: 
    new_solution = [] 
    #Try to get unique values from each previous set 
    try: 
     for sol_set in solution_sets: 
      while True: 
       candidate = sol_set.pop() 
       if not candidate in used: 
        new_solution.append(candidate) 
        used.update([candidate]) 
        break 
    except KeyError, e: 
     print e 
     break 
    #Fill with new data until the line is long enough 
    try: 
     while len(new_solution) < SET_LENGTH: 
      new_solution.append(data.pop()) 
    except KeyError, e: 
     print e 
     break 
    solutions.append(new_solution) 
    solution_sets.append(set(new_solution)) 
#Show the results 
for solution in solutions: 
    print solution 
print "Orphans %s" % len(data) 

N = 300 X = 10 개 수율 :

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
[0, 10, 11, 12, 13, 14, 15, 16, 17, 18] 
[1, 10, 19, 20, 21, 22, 23, 24, 25, 26] 
[2, 11, 19, 27, 28, 29, 30, 31, 32, 33] 
[3, 12, 20, 32, 34, 35, 36, 37, 38, 39] 
[4, 13, 21, 33, 34, 40, 41, 42, 43, 44] 
[5, 14, 22, 27, 36, 40, 45, 46, 47, 48] 
[6, 15, 23, 28, 37, 41, 45, 49, 50, 51] 
[7, 16, 24, 29, 38, 42, 47, 49, 52, 53] 
[8, 17, 25, 30, 39, 43, 48, 50, 52, 54] 
[9, 18, 26, 31, 35, 44, 46, 51, 53, 54] 
Orphans 245 

당신이 얼마나 많은 솔루션 다음 같은 공통 요소를 공유 상관하지 않는 경우 더 쉽게 :

SET_LENGTH = 2 
CHOICE_LENGTH = 300 

data = set(range(CHOICE_LENGTH)) 
solutions =[] 
alpha = data.pop() 
while True: 
    new_solution = [alpha] 
    try: 
     [new_solution.append(data.pop()) for x in range(SET_LENGTH-1)] 
    except KeyError, e: 
     break 
    solutions.append(new_solution) 

for solution in solutions: 
    print solution 
print "Solutions: %s" % len(solutions) 
print "Orphans: %s" % len(data)