全排列算法的非递归实现与递归实现的方法(C++)
2019/7/10 23:27:07
本文主要是介绍全排列算法的非递归实现与递归实现的方法(C++)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
（一）非递归全排列算法
基本思想是:
1.找到所有排列中最小的一个排列P.
2.找到刚刚好比P大比其它都小的排列Q,
3.循环执行第二步,直到找到一个最大的排列,算法结束.
下面用数学的方法描述:
给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )
找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)
从Pmin开始,总是目前得到的最大的排列为输入,得到下一个排列.
方法为:
1.从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个Pi，使Pi < P(i+1)。
若找不到这样的pi，说明我们已经找到最后一个全排列，可以返回了。
2.在 P(i+1)P(i+2)Pn 中,找到一个Pj,便得 Pj"刚刚好大于"Pi.
("刚刚好大于"的意思是:在 P(i+1)P(i+2)Pn 中所有大于Pi的元素构成的集合中最小的元素.)
3.交换 Pi , Pj 的位置.注意:此处不改变i和j的值,改变的是Pi和Pj.
4.交换后， P1P2P3Pn 并不是准确的后一个排列。因为根据第1步的查找，我们有P(i+1) > P(i+2) > . > Pn
即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.
//交换数组a中下标为i和j的两个元素的值
void swap(int* a,int i,int j)
{
a[i]^=a[j];
a[j]^=a[i];
a[i]^=a[j];
}
//将数组a中的下标i到下标j之间的所有元素逆序倒置
void reverse(int a[],int i,int j)
{
for(;i<j;++i,--j)
{
swap(a,i,j);
}
}
void print(int a[],int length)
{
for(int i=0;i<length;++i)
cout<<a[i]<<" ";
cout<<endl;
}
//求取全排列，打印结果
void combination(int a[],int length)
{
if(length<2) return;
bool end=false;
while(true)
{
print(a,length);
int i,j;
//找到不符合趋势的元素的下标i
for(i=length-2;i>=0;--i)
{
if(a[i]<a[i+1]) break;
else if(i==0) return;
}
for(j=length-1;j>i;--j)
{
if(a[j]>a[i]) break;
}
swap(a,i,j);
reverse(a,i+1,length-1);
}
}
（二）递归算法
令E= {e1 , ..., en }表示n 个元素的集合，我们的目标是生成该集合的所有排列方式。令Ei 为E中移去元素i 以后所获得的集合，perm (X) 表示集合X 中元素的排列方式，ei . p e r m(X)表示在perm (X) 中的每个排列方式的前面均加上ei 以后所得到的排列方式。例如，如果E= {a, b, c}，那么E1= {b, c}，perm (E1 ) = ( b c, c b)，e1 .perm (E1) = (a b c, a c b)。对于递归的基本部分，采用n = 1。当只有一个元素时，只可能产生一种排列方式，所以perm (E) = ( e)，其中e 是E 中的唯一元素。当n > 1时，perm (E) = e1 .perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) + ⋯ +en .perm (En )。这种递归定义形式是采用n 个perm (X) 来定义perm (E), 其中每个X 包含n- 1个元素。至此，一个完整的递归定义所需要的基本部分和递归部分都已完成。
当n= 3并且E=（a, b, c）时，按照前面的递归定义可得perm (E) =a.perm ( {b, c} ) +b.perm ( {a,c} ) +c.perm ( {a, b} )。同样，按照递归定义有perm ( {b, c} ) =b.perm ( {c} ) +c.perm ( {b}), 所以a.perm ( {b, c} ) = ab.perm ( {c} ) + ac.perm ( {b}) = a b . c + ac.b = (a b c, a c b)。同理可得b.perm ( {a, c}) = ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a)，c.perm ( {a, b}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a)。所以perm (E) = (a b c, a c b, b a c, b c a,c a b, c b a)。注意a.perm ( {b, c} )实际上包含两个排列方式：abc 和a c b，a 是它们的前缀，perm ( {b, c} )是它们的后缀。同样地，ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。程序1 - 1 0把上述perm (E) 的递归定义转变成一个C++ 函数，这段代码输出所有前缀为l i s t [ 0：k-1], 后缀为l i s t [ k：m] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方式，在该调用中，k=0, m= n - 1，因此排列方式的前缀为空，后缀为list[0: n-1] 产生的所有排列方式。当k =m 时，仅有一个后缀l i s t [ m ]，因此list[0: m] 即是所要产生的输出。当k<m时，先用list[k] 与l i s t [ k：m] 中的每个元素进行交换，然后产生list[k+1: m] 的所有排列方式，并用它作为list[0: k] 的后缀。S w a p是一个inline 函数，它被用来交换两个变量的值
template <class T>
inline void Swap(T& a, T& b)
{
// 交换a和b
T temp = a; a = b; b = temp;
}
template<class T>
void Perm(T list[], int k, int m)
{
//生成list [k：m ]的所有排列方式
int i;
if (k == m)
{
//输出一个排列方式
for (i = 0; i <= m; i++)
cout << list [i];
cout << endl;
}
else // list[k：m ]有多个排列方式
{
// 递归地产生这些排列方式
for (i=k; i <= m; i++)
{
Swap (list[k], list[i]);
Perm (list, k+1, m);
Swap (list [k], list [i]);
}
}
}
基本思想是:
1.找到所有排列中最小的一个排列P.
2.找到刚刚好比P大比其它都小的排列Q,
3.循环执行第二步,直到找到一个最大的排列,算法结束.
下面用数学的方法描述:
给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )
找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)
从Pmin开始,总是目前得到的最大的排列为输入,得到下一个排列.
方法为:
1.从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个Pi，使Pi < P(i+1)。
若找不到这样的pi，说明我们已经找到最后一个全排列，可以返回了。
2.在 P(i+1)P(i+2)Pn 中,找到一个Pj,便得 Pj"刚刚好大于"Pi.
("刚刚好大于"的意思是:在 P(i+1)P(i+2)Pn 中所有大于Pi的元素构成的集合中最小的元素.)
3.交换 Pi , Pj 的位置.注意:此处不改变i和j的值,改变的是Pi和Pj.
4.交换后， P1P2P3Pn 并不是准确的后一个排列。因为根据第1步的查找，我们有P(i+1) > P(i+2) > . > Pn
即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.
复制代码 代码如下:
//交换数组a中下标为i和j的两个元素的值
void swap(int* a,int i,int j)
{
a[i]^=a[j];
a[j]^=a[i];
a[i]^=a[j];
}
//将数组a中的下标i到下标j之间的所有元素逆序倒置
void reverse(int a[],int i,int j)
{
for(;i<j;++i,--j)
{
swap(a,i,j);
}
}
void print(int a[],int length)
{
for(int i=0;i<length;++i)
cout<<a[i]<<" ";
cout<<endl;
}
//求取全排列，打印结果
void combination(int a[],int length)
{
if(length<2) return;
bool end=false;
while(true)
{
print(a,length);
int i,j;
//找到不符合趋势的元素的下标i
for(i=length-2;i>=0;--i)
{
if(a[i]<a[i+1]) break;
else if(i==0) return;
}
for(j=length-1;j>i;--j)
{
if(a[j]>a[i]) break;
}
swap(a,i,j);
reverse(a,i+1,length-1);
}
}
（二）递归算法
令E= {e1 , ..., en }表示n 个元素的集合，我们的目标是生成该集合的所有排列方式。令Ei 为E中移去元素i 以后所获得的集合，perm (X) 表示集合X 中元素的排列方式，ei . p e r m(X)表示在perm (X) 中的每个排列方式的前面均加上ei 以后所得到的排列方式。例如，如果E= {a, b, c}，那么E1= {b, c}，perm (E1 ) = ( b c, c b)，e1 .perm (E1) = (a b c, a c b)。对于递归的基本部分，采用n = 1。当只有一个元素时，只可能产生一种排列方式，所以perm (E) = ( e)，其中e 是E 中的唯一元素。当n > 1时，perm (E) = e1 .perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) + ⋯ +en .perm (En )。这种递归定义形式是采用n 个perm (X) 来定义perm (E), 其中每个X 包含n- 1个元素。至此，一个完整的递归定义所需要的基本部分和递归部分都已完成。
当n= 3并且E=（a, b, c）时，按照前面的递归定义可得perm (E) =a.perm ( {b, c} ) +b.perm ( {a,c} ) +c.perm ( {a, b} )。同样，按照递归定义有perm ( {b, c} ) =b.perm ( {c} ) +c.perm ( {b}), 所以a.perm ( {b, c} ) = ab.perm ( {c} ) + ac.perm ( {b}) = a b . c + ac.b = (a b c, a c b)。同理可得b.perm ( {a, c}) = ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a)，c.perm ( {a, b}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a)。所以perm (E) = (a b c, a c b, b a c, b c a,c a b, c b a)。注意a.perm ( {b, c} )实际上包含两个排列方式：abc 和a c b，a 是它们的前缀，perm ( {b, c} )是它们的后缀。同样地，ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。程序1 - 1 0把上述perm (E) 的递归定义转变成一个C++ 函数，这段代码输出所有前缀为l i s t [ 0：k-1], 后缀为l i s t [ k：m] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方式，在该调用中，k=0, m= n - 1，因此排列方式的前缀为空，后缀为list[0: n-1] 产生的所有排列方式。当k =m 时，仅有一个后缀l i s t [ m ]，因此list[0: m] 即是所要产生的输出。当k<m时，先用list[k] 与l i s t [ k：m] 中的每个元素进行交换，然后产生list[k+1: m] 的所有排列方式，并用它作为list[0: k] 的后缀。S w a p是一个inline 函数，它被用来交换两个变量的值
复制代码 代码如下:
template <class T>
inline void Swap(T& a, T& b)
{
// 交换a和b
T temp = a; a = b; b = temp;
}
template<class T>
void Perm(T list[], int k, int m)
{
//生成list [k：m ]的所有排列方式
int i;
if (k == m)
{
//输出一个排列方式
for (i = 0; i <= m; i++)
cout << list [i];
cout << endl;
}
else // list[k：m ]有多个排列方式
{
// 递归地产生这些排列方式
for (i=k; i <= m; i++)
{
Swap (list[k], list[i]);
Perm (list, k+1, m);
Swap (list [k], list [i]);
}
}
}
这篇关于全排列算法的非递归实现与递归实现的方法(C++)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23增量更新怎么做？-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些？-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗？-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处？-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享
