这题的本质其实是解答树的dfs 回溯法就可以解决 对于next_permutation 本人不是很反对 我的观点是就像手写merge_sort和STL中的sort一样 各有千秋罢了 还有都是竞赛生 这种水题的方法就没必要了

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int ans[N];
bool vis[N];
int n;

void dfs(int k)
{
	if(k>n)
	{
		for(int i = 1;i<=n;i++) cout << ans[i] << " ";
		cout << endl;
		return ; 
	}
	for(int i = 1;i<=n;i++)
	{
		if(vis[i])
		{
			ans[k] = i;
			vis[i] = false;
			dfs(k+1);
			vis[i] = true;
		}
	}
}

int main()
{
	cin >> n;
	memset(vis,true,sizeof(vis));
	dfs(1);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,sum=1,a[9];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		a[i]=n-i+1;sum*=i;
	}
	for(int i=1;i<=sum;i++)
	{
		{
			next_permutation(a+1,a+n+1);
			for(int k=1;k<=n;k++)
			{
				cout<<a[k]<<" ";
			}
			cout<<endl;
		}
	}
}

next_permutation自动生成数组下一个字典序排序

C++ :

#include <iostream>
#include <cstdio>
using namespace std;
int fac(int m){
    if(m==1 || m==0){return 1;}
    else return m*(m-1);
}
int main()
{
    printf("1 2 3\n1 3 2\n2 1 3\n2 3 1\n3 1 2\n3 2 1");
    return 0;
}

一种神奇的python方法（一开始我都没想过这会过）

def f(x):
	if x==0:
		return 1
	else:
		return f(x-1)*x


n=int(input())
for i in range(f(n)):
	a=list(range(1,n+1))
	for j in range(n):
		b=a[((i)//f(n-j-1))%len(a)]
		print(b,end=' ')
		a.remove(b)
	print('')

#include<bits/stdc++.h>

using namespace std;
int main() 
{
	const int N = 9;
	int Y[N];
	int a;
	int f = 1;//同时用来赋值和统计数字数量
	cin >> a;
	int sum = 1;//统计行数
	Y[0] = 0;
	for (int n = 1; n <= a ; n++)
	{
		sum = sum * f;//行数等于各位数之积
		Y[n] = f;
		f++;
		
	}
	for (int g = 1; g <= f-1; g++)//输出原版
	{
		cout << Y[g] << " ";
	}
	cout << endl;
	for (int g = 0; g <= sum - 1; g++)//行数
	{
		next_permutation(Y, Y +f);//自动按字典序排列
		for (int o = 1; o <= f-1; o++)//排列之后输出
		{
			if (Y[o] == 0)
				break;
			cout << Y[o] << " ";
			
		}
		cout << endl;
	}
	
}

自动把1，2，3退到最后了，但又提前输出了，所以后面循环终止