15649 N과 M(1)

N과 M (1)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1504	933	665	65.260%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

순열과 조합의 순열을 묻는 문제이다.

순열을 구하는 것을 코드로 구현하자면 내 머리로는 복잡하다.

간략히 말해보면 각 길이만큼 2차원 리스트들을 뽑아놓고 1의 자리 부터 세로로 쭉 나열하고 

1의 자리 로테이션이 1번 돌면 10의 자리 커서가 아래로 이동하면서 차례로 입력하는 순이다.

하지만 파이썬에서는 from itertools import permutations 으로 간단히 구현할 수 있다.

물론 중복없는 순열이다.

permutations(iterable, length)

combinations

products 도 가능.

아래는 구현 코드 

from itertools import permutations

n,m = map(int, input().split())

temp = permutations(range(1,n+1,1),m)

for i in temp:

    print( str(i)[1:-1].replace(",","") )

아래는 중복있는 수열을 만드는 알고리즘을 설명한 것이다.

http://swlock.blogspot.com/2016/11/permutation-combination-algorithm-full.html

위를 바탕으로 문제를 풀어보았다 itertools 사용x

import sys

import math

sys.stdin = open("input.txt","r",encoding="utf-16")

n,m = map(int, input().split())

answer = []

for i in range(m):

answer.append("")

def cal_perm(deepness):

if deepness == m:

print( str(answer)[1:-1].replace(",","") )

else:

for i in range(1,n+1,1):

if i not in answer:

answer[deepness] = i

cal_perm(deepness+1)

answer[deepness] = -1

cal_perm(0)