매트릭스에서 조건부 배열 필터링

Question

스웨덴에서는 13 개의 경기 결과를 찾으려고하는 축구 (축구) 베팅 게임이 있습니다. 각 경기가 홈에서 승리 할 수 ​​있기 때문에 무승부 또는 어웨이 팀이 승리하면 3 ** 13 = 1594323 건의 결과가 발생할 수 있습니다. 10 ~ 13 경기가 정확하면 승리합니다. 상금 합계가 모든 수상자로 나뉘기 때문에 많은 사람들이 높은 점수를 얻었을 때이 현상이 발생하기를 원하지 않습니다. 이것은 좀 더 일반적인 질문의 배경입니다 : 행렬 내의 주어진 배열로부터 최소한 x 요소만큼 다른 모든 배열을 찾는 법 (이 경우 1594323 * 13)입니다.

내 마음에 처음 나온 명백한 아이디어는 13 개의 루프를 중첩 시켜서 한 번에 하나의 배열을 비교하는 것이 었습니다. 그러나이 문제를 파이썬 프로그래밍을 배우기위한 교육 세션으로 사용하고 있습니다. 파이썬은 이런 종류의 작업을위한 최적의 도구가 아니며 빠른 프로그램을 얻기 위해 C로 변할 수 있지만 최선의 알고리즘에 관심이 있습니다.

파이썬에서 중첩 된 for 루프 메서드를 최대 10 개 일치 시키려고 시도했습니다. 그런 다음 실행 시간이 내가 사용하는 netbook에서 5 초가 너무 길어졌습니다. 추가 된 매치마다 실행 시간이 10 배가되었습니다.

또 다른 접근법은 데이터베이스를 사용하는 것이고 해결책 일 수도 있지만 이런 종류의 문제를 해결하는 가장 빠른 방법은 무엇인지 궁금합니다. 짧은 검색에서 문제의 정확한 설명을 사용하기가 어려워서이 문제를 성공적으로 찾지 못했습니다.

Answer 1

x 값이 0 (최악의 경우) 일 때 내 컴퓨터에서 약 5 초 후에 종료되는 재귀 적 솔루션입니다. x 값이 10 이상이면 거의 즉각적입니다.

def arrays_with_differences(arr, x): 
    if x > len(arr): 
     return [] 

    if len(arr) == 0: 
     return [[]] 

    smallColl1 = arrays_with_differences(arr[:len(arr)-1], x) 
    smallColl2 = arrays_with_differences(arr[:len(arr)-1], x-1) 

    last = arr[len(arr)-1] 
    altLast1 = (last + 1) % 3 
    altLast2 = (last + 2) % 3 

    result = [smallArr + [last] for smallArr in smallColl1] 
    result.extend([smallArr + [altLast1] for smallArr in smallColl2]) 
    result.extend([smallArr + [altLast2] for smallArr in smallColl2]) 
    return result 

result = arrays_with_differences([1,0,1,0,1,1,1,1,1,1,1,1,1], 4) 
print(len(result))