［試験符号化／規格］NおよびM(1)

🔍NとM(1)

<質問>
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.

1からNまで、自然水体中でM個の数列

を繰り返し選択する.
<入力>
第1行は自然数NとMを与える.(1 ≤ M ≤ N ≤ 8)
<出力>
各行に問題条件を満たす数列を出力します.重複する数列は複数回出力できません.各数列はスペースで区切らなければなりません.
数列は予め増加した順序で出力しなければならない.

他人のコード

考えてみると、どうやって解くか分からず、他人のコードを見ることにした.
🔗コメント
https://wlstyql.tistory.com/56
1.この解法は分かりにくい.

N, M = map(int, input().split())
visited = [False] * N  # 탐사 여부 check
out = []  # 출력 내용

def solve(depth, N, M):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, out)))  # list를 str으로 합쳐 출력
        return
    for i in range(len(visited)):  # 탐사 check 하면서
        if not visited[i]:  # 탐사 안했다면
            visited[i] = True  # 탐사 시작(중복 제거)
            out.append(i+1)  # 탐사 내용
            solve(depth+1, N, M)  # 깊이 우선 탐색
            visited[i] = False  # 깊이 탐사 완료
            out.pop()  # 탐사 내용 제거

solve(0, N, M)

NとMを入力します.

の配列と出力内容の配列を探査するかどうかを確認する生成.

アクセスの長さ(N)の範囲内で、インデックスiがプローブされていない場合、アクセス[i]=Trueをプローブ(重複除外)を示す代わりにし、プローブコンテンツ(インデックスは0から始まるので、i+1)を出力コンテンツ配列に付加する.

であり、depth+1によって再帰関数を解く.

の深部検出が完了すると、アクセス[i]をFalseに変換し、検出内容を削除します.

深さがMと同じである場合、コンテンツ配列が出力される.

2.Python内部関数itertoolsの配列(重複しないシーケンス検索)を用いて解く.

from itertools import permutations
N, M = map(int, input().split())
P = permutations(range(1, N+1), M)  # iter(tuple)
for i in P:
    print(' '.join(map(str, i)))  # tuple -> str

リストの中のすべての値の組み合わせを求めます

🔗リファレンス
https://ourcstory.tistory.com/414
Pythonでは、Pythonベースライブラリitertoolsを使用して、リスト内のすべての値の組合せを簡単に取得できます.

from itertools import product
from itertools import permutations
from itertools import combinations

1つのリストですべての組合せを計算する必要がある場合、->配列、組合せを使用します.
2つ以上のリストですべての組合せを計算する必要がある場合は、->製品を使用します.
permutations
配列(シーケンス)とは、順番にリストされる数がいくつか選択されていることを意味します.すなわち,異なるnにおいて,r個の順に配列されたダミー数を選択する.

items = ['1', '2', '3', '4', '5']
from itertools import permutations
list(permutations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '1'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '1'), ('3', '2'), ('3', '4'), ('3', '5'), ('4', '1'), ('4', '2'), ('4', '3'), ('4', '5'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4')]

combinations
コンビネーション(コンビネーション)は、異なるnでr個(n≧r)を1つのグループとした場合に、各グループをnでr個と呼ぶコンビネーションである.

items = ['1', '2', '3', '4', '5']
from itertools import combinations
list(combinations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]

product

from itertools import product
items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))
# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]

🔗Baekjun-NとM(1)
https://www.acmicpc.net/problem/15649