04070: 全排列

recursion, http://cs101.openjudge.cn/practice/04070/

对于数组[1, 2, 3]，他们按照从小到大的全排列是

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

现在给你一个正整数n，n小于8，输出数组[1, 2, …，n]的从小到大的全排列。

输入

输入有多行，每行一个整数。当输入0时结束输入。

输出

对于每组输入，输出该组的全排列。每一行是一种可能的排列，共n个整数，每个整数用一个空格隔开，每行末尾没有空格。

样例输入

2
3
0

样例输出

1 2
2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

def dfs(n, path, used, res):
    if len(path) == n:
        res.append(path[:])
        return
    for i in range(1, n+1):
        if not used[i]:
            used[i] = True
            path.append(i)
            dfs(n, path, used, res)
            path.pop()
            used[i] = False

def print_permutations(n):
    res = []
    dfs(n, [], [False]*(n+1), res)
    for perm in sorted(res):
        print(' '.join(map(str, perm)))

nums = []
while True:
    num = int(input())
    if num == 0:
        break
    nums.append(num)

for num in nums:
    print_permutations(num)