全排列算法问全排列公式解释

全排列算法  时间:2021-08-31  阅读:()

求遍历全排列的算法

全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

常见的有四种全排列算法: (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 这里着重介绍字典序法 对给定的字符集中的字符规定了一个先后关系,在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一个全排列可看做一个字符串,字符串可有前缀、后缀。

1)生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有其他的。

这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。

[例]839647521是1--9的排列。

1—9的排列最前面的是123456789,最后面的是987654321,从右向左扫描若都是增的,就到了987654321,也就没有下一个了。

否则找出第一次出现下降的位置。

谁知C++求全排列的算法

#include <iostream> #include <string> #include <list> using namespace std; string slist=""; string sresult=""; int listlen=0; int ex=0; string permute(string list) { string strreturn=""; int ln=list.length(); if( ln==2 ) { strreturn=list; char temp; temp=list[0]; list[0]=list[1]; list[1]=temp; return strreturn+list; } string substr=""; string strtemp=""; for(int i=0; i<ln; ++i) { strtemp.clear(); substr.clear(); if( i>0 ) substr += list.substr(0,i); if( i<ln-1 ) substr += list.substr(i+1, ln-1); int lntemp=ln-1; long FN=lntemp; while( --lntemp!=1 ) FN*=lntemp; lntemp=ln-1; string str=permute(substr); for(int j=0; j<FN; ++j) { strtemp += list[i]+str.substr(j*lntemp, lntemp); } strreturn += strtemp; } return strreturn; } int main() { cout<<"Enter the characters to permute: "; getline(cin, slist); listlen = slist.length()-1; slist = slist.substr(0, listlen); sresult=permute(slist); int lntemp=listlen; long FN=lntemp; while( --lntemp!=1 ) FN*=lntemp; //排除有3个连续字母的... string str=""; lntemp=listlen; for(int i=0; i<FN; ++i) { str=sresult.substr(i*lntemp, lntemp); for( int j=0; j<lntemp-2; ++j ) { if( str[j]==str[j+1]-1 && str[j+1]==str[j+2]-1 ) { sresult.erase( i*lntemp, lntemp ); //删除之 --i; --FN; cout<<str<<"..."; //显示被排除的排列 break; } } } cout<<endl; for(int i=0; i<FN; ++i) { str=sresult.substr(i*lntemp, lntemp); cout<<str<<"..."; } cout<<FN<<endl; //符合要求的排列数 }

java 全排列算法;

= =~思路什么的...用递归吧: package mon_11; import java.util.HashSet; public class ArrangeAll { private static HashSet<String> set = new HashSet<String>(); public static void arrangeAll(String s) { put(new StringBuilder(s), new StringBuilder()); } static void put(StringBuilder s1, StringBuilder s2) { if (s1.length() == 0)set.add(s2.toString()); for (int i = 0; i < s1.length(); i++) { put(new StringBuilder(s1).deleteCharAt(i),new StringBuilder(s2).append(s1.charAt(i))); } } public static void main(String[] args) { arrangeAll("abcd"); System.out.println(set); } } ---- 输出: [dcab, acdb, acbd, bcda, bdca, bdac, dbca, bacd, cabd, cdba, cdab, badc, dabc, cadb, dbac, bcad, dacb, cbda, cbad, adbc, adcb, abcd, abdc, dcba]

问全排列公式解释

可以这样解释: 第一次取球有8种可能,我们放在第一位; 第二次取球有7种可能(因为第一次已取走一个),我们放在第二位; 第三次取球有6种肯能(因为前两次已取走两个),我们放在第三位; 所以共有8*7*6种排列方法。

但是我们只要求球不同,而位置没要求, 那么三个位置,相同的一组三个球,有几种排列呢,6种,分别为: 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1。

所以如果不要求位置,三个球的组合为8*7*6/6=56。

如果是排列P83=8!/5!; 而组合是C83=P!/3! 不知我说明白了吗?

HostKvm($4.25/月)俄罗斯/香港高防VPS

HostKvm又上新了,这次上架了2个线路产品:俄罗斯和香港高防VPS,其中俄罗斯经测试电信CN2线路,而香港高防VPS提供30Gbps攻击防御。HostKvm是一家成立于2013年的国外主机服务商,主要提供基于KVM架构的VPS主机,可选数据中心包括日本、新加坡、韩国、美国、中国香港等多个地区机房,均为国内直连或优化线路,延迟较低,适合建站或者远程办公等。俄罗斯VPSCPU:1core内存:2G...

旅途云(¥48 / 月),雅安高防4核4G、洛阳BGP 2核2G

公司成立于2007年,是国内领先的互联网业务平台服务提供商。公司专注为用户提供低价高性能云计算产品,致力于云计算应用的易用性开发,并引导云计算在国内普及。目前,旅途云公司研发以及运营云服务基础设施服务平台(IaaS),面向全球客户提供基于云计算的IT解决方案与客户服务,拥有丰富的国内BGP、双线高防、香港等优质的IDC资源。点击进入:旅途云官方网商家LOGO优惠方案:CPU内存硬盘带宽/流量/防御...

iWebFusion:独立服务器月付57美元起/5个机房可选,10Gbps服务器月付149美元起

iWebFusion(iWFHosting)在部落分享过很多次了,这是成立于2001年的老牌国外主机商H4Y旗下站点,提供的产品包括虚拟主机、VPS和独立服务器租用等等,其中VPS主机基于KVM架构,数据中心可选美国洛杉矶、北卡、本德、蒙蒂塞洛等。商家独立服务器可选5个不同机房,最低每月57美元起,而大流量10Gbps带宽服务器也仅149美元起。首先我们分享几款常规服务器配置信息,以下机器可选择5...

全排列算法为你推荐
对称矩阵实对称矩阵是什么意思?云和数据黑马和云和数据哪家好?有啥区别公告格式通知的格式。竞争者市场营销学中的竞争者有哪些主要类型?权限表什么是权限表?权限表有什么功能?组或资源的状态不是执行请求操作的正确状态无法启动承载网络,组或资源状态下不是执行请求操作的正确状态!支付宝证书网上证书 支付宝网不易小学生上网弊大于利网不易wifi上网有什么优点和缺点零终端什么是圈存机
虚拟主机测评 vps服务器租用 山东vps 万网域名解析 荣耀欧洲 singlehop 韩国俄罗斯 linode 海外服务器 香港托管 抢票工具 地址大全 linux空间 微信收钱 vip购优汇 100m空间 ntfs格式分区 1美金 如何安装服务器系统 网购分享 更多