[スタンダード/python]DFS/BFS-6603号宝くじ



👩🏻‍🏫 に答える

import sys

# 재귀함수를 이용한 조합 구현
def combination(arr, n):
  result = []
  if n == 0:
    return [[]]
  for i in range(len(arr)):
    elem = arr[i]
    for rest in combination(arr[i+1:],n-1):
      result.append([elem]+rest)
  return result

nums = [] 
while True:
  lst = list(map(int,sys.stdin.readline().split()))
  if lst[0] == 0:
    break
  del lst[0]
  for i in combination(lst,6): 
    for j in i:
      print(j, end=" ")
    print()
  print()
  • 混同部分:入力はすべて受け取ったと思って、テストケースの順序で出力すべきだと思っていましたが、事実はそうではありません.
  • # 출력
    7 1 2 3 4 5 6 7
    1 2 3 4 5 6 
    1 2 3 4 5 7 
    1 2 3 4 6 7 
    1 2 3 5 6 7 
    1 2 4 5 6 7 
    1 3 4 5 6 7 
    2 3 4 5 6 7 
    
    8 1 2 3 5 8 13 21 34
    1 2 3 5 8 13 
    1 2 3 5 8 21 
    1 2 3 5 8 34 
    1 2 3 5 13 21 
    1 2 3 5 13 34 
    1 2 3 5 21 34 
    1 2 3 8 13 21 
    1 2 3 8 13 34 
    1 2 3 8 21 34 
    1 2 3 13 21 34 
    1 2 5 8 13 21 
    1 2 5 8 13 34 
    1 2 5 8 21 34 
    1 2 5 13 21 34 
    1 2 8 13 21 34 
    1 3 5 8 13 21 
    1 3 5 8 13 34 
    1 3 5 8 21 34 
    1 3 5 13 21 34 
    1 3 8 13 21 34 
    1 5 8 13 21 34 
    2 3 5 8 13 21 
    2 3 5 8 13 34 
    2 3 5 8 21 34 
    2 3 5 13 21 34 
    2 3 8 13 21 34 
    2 5 8 13 21 34 
    3 5 8 13 21 34 
    
    0

    ▼▼▼数式


    シーケンス(Permutation)

  • nPr=n!(n−r)!nPr= { n!\over(n-r)!}nPr=(n−r)!n!​

  • 個の異なるnnnからrrr個を順次選択する数は
  • である.

    コンポジット

  • nCr=n!(n−r)!r!nCr= { n!\over(n-r)! r!}nCr=(n−r)!r!n!​

  • 個の異なるnnnからrrr個をランダムに選択する数は
  • である.

    繰り返しシーケンス

  • nΠr=nrnΠr=n^rnΠr=nr

  • 個の異なるnnnからrrr個を繰り返し可能な順序で選択する数は
  • である.

    くりかえしくみたて

  • nHr=n+r−𝟏Cr=(n+r−1)!(n−1)!r!nHr= n+r-𝟏Cr = { (n+r-1)!\over(n-1)! r!}nHr=n+r−1Cr=(n−1)!r!(n+r−1)!​

  • 個の異なるnnnからランダムに選択するRRR個の数は
  • である.

    ✏️ Python


    再帰関数を使用した組合せ

  • 基本アイデアcombination([0,1,2,3],2) =([0], combination([1,2,3], 1)) +([1], combination([2,3], 1)) +([2], combination([3], 1))
  • コード
  • def combination(arr,n):
    	result = []
    	if n == 0:
        	return [[]]
        for i in range(len(arr)):
        	elem = arr[i]
            for rest in combination(arr[i+1:],n-1):
            	result.append([elem] + rest)
        return result
    
    print(combination([0,1,2,3],2)   # [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]   

    再帰関数を使用したシーケンスの実装

  • 基本アイデアpermutation([0,1,2,3],2) =([0], combination([1,2,3], 1)) +([1], combination([0,2,3], 1)) +([2], combination([0,1,3], 1)) +([3], combination([0,1,2], 1))
  • コード
  • def permutaion(arr,n):
    	result = []
        if n == 0:
        	return [[]]
        for i in range(len(arr)):
        	elem = arr[i]
            for rest permuation(arr[:i] + arr[i+1:], n-1):
            	resutl.append([elem] + rest)
        return result
    
    print(permutation([0,1,2,3],2)   #[[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]
    
    https://kjhoon0330.tistory.com/15