全排列演算法
① 全排列計算公式是什麼
全排列的排列數公式為n！，通過乘法原理可以得到。
從n個數中選取m（m<=n）個數按照一定的順序進行排成一個列，叫作從n個元素中取m個元素的一個排列。
由排列的定義，顯然不同的順序是一個不同的排列。
從n個元素中取m個元素的所有排列的個數，稱為排列數。
從n個元素取出n個元素的一個排列，稱為一個全排列。
全排列的排列數公式為n！，通過乘法原理可以得到。
列出全排列的初始思想：
我們現在做這樣的一個假設，假設給定的一些序列中第一位都不相同，那麼就可以認定說這些序列一定不是同一個序列，這是一個很顯然的問題。
有了上面的這一條結論，我們就可以同理得到如果在第一位相同，可是第二位不同，那麼在這些序列中也一定都不是同一個序列。
② 求全排列的演算法
組合數學書裡面有。
③ 如何生成一串數字的全排列 演算法
個人一點見解，希望對你有所幫助。
依我之見，你的對換部分出了一點點問題。只要作如下修改即可：
1、exchange 改為：
procere exchange(l,r:integer);
var
t,len:integer;
begin
if l=r then exit;
len:=r-l+1;
len:=len div 2;
for i:=1 to len do
begin
t:=a[l+i-1];
a[l+i-1]:=a[r-i+1];
a[r-i+1]:=t;
end;
end;
2、主過程中exchange(p,n)改為exchange(i+1,n)。
④ 全排列演算法問題。。。。高手進。。謝謝。。
perm(list,k+1,m);//這里原來list後面的逗號是中文的，需要改為西文字元
⑤ 關於全排列演算法實現（請幫忙注釋這些代碼）
全排列用的是
置換演算法，
演算法這東西重在理解。具體代碼並不那麼重要。
全排列是將一組數按一定順序進行排列，如果這組數有n個，那麼全排列數為n!個。現以{1,
2,
3,
4,
5}為
例說明如何編寫全排列的遞歸演算法。
1、首先看最後兩個數4,
5。
它們的全排列為4
5和5
4,
即以4開頭的5的全排列和以5開頭的4的全排列。
由於一個數的全排列就是其本身，從而得到以上結果。
2、再看後三個數3,
4,
5。它們的全排列為3
4
5、3
5
4、
4
3
5、
4
5
3、
5
3
4、
5
4
3
六組數。
即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.
從而可以推斷，設一組數p
=
{r1,
r2,
r3,
...
,rn},
全排列為perm(p)，pn
=
p
-
{rn}。
因此perm(p)
=
r1perm(p1),
r2perm(p2),
r3perm(p3),
...
,
rnperm(pn)。當n
=
1時perm(p}
=
r1。
為了更容易理解，將整組數中的所有的數分別與第一個數交換，這樣就總是在處理後n-1個數的全排列。
演算法如下：
#include
<stdio.h>
int
n
=
0;
void
swap(int
*a,
int
*b)
{
int
m;
m
=
*a;
*a
=
*b;
*b
=
m;
}
void
perm(int
list[],
int
k,
int
m)
{
int
i;
if(k
>
m)
{
for(i
=
0;
i
<=
m;
i++)
printf("%d
",
list[i]);
printf("\n");
n++;
}
else
{
for(i
=
k;
i
<=
m;
i++)
{
swap(&list[k],
&list[i]);
perm(list,
k
+
1,
m);
swap(&list[k],
&list[i]);
}
}
}
int
main()
{
int
list[]
=
{1,
2,
3,
4,
5};
perm(list,
0,
4);
printf("total:%d\n",
n);
return
0;
}
⑥ java 全排列演算法
遞歸實現，取數字（字元串）中第i個位置的字元，然後將他和剩餘的字元拼接，剩餘的字元串當成有一個全排列的輸入，這樣遞歸下去，只剩一個字元時全排列就是本身。程序中使用set去除了重復的數據，如果需要保留，將set換為list介面即可。
package mytest;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/*
* @date:2012-2-8
* @author:
*
* 輸入一個數字，講輸出 1到這個數字的全排列
*/
public class MyDemo2 {
private static Set<String> SET_STRING = new HashSet<String>();
private static Set<Long> SET_NUM = new HashSet<Long>();
public static void main(String[] args) {
System.out.println("begin ...... ");
testLong(234);
testString("a23");
print(SET_NUM);
print(SET_STRING);
System.out.println("end ...... ");
}
/**
* 測試數字
* @param num
*/
private static void testLong(long num){
long testNum = num;
String[] permutation;
for(long l=0; l<=testNum; l++){
permutation = getAllOrder(String.valueOf(l));
for (int i = 0; i < permutation.length; i++) {
SET_NUM.add(Long.valueOf(permutation[i]));
}
}
}
/**
* 測試字元串
* @param str
*/
private static void testString(String str){
String[] permutation = getAllOrder(str);
for (int i = 0; i < permutation.length; i++) {
SET_STRING.add(permutation[i]);
}
}
private static void print(Set set){
System.out.println("/*****************************************************/");
int i=0;
for(Iterator it = set.iterator(); it.hasNext();){
i++;
if(i%10 == 0){
System.out.println();
}
System.out.print(it.next() + " ");
}
System.out.println();
System.out.println("/*****************************************************/");
}
/**
* 遞歸演算法 全排列 去除重復
* @param str
* @return
*/
private static String[] getAllOrder(String str) {
String [] arrResult = null;
Set<String> set = new HashSet<String>();
if(str.length()>1){
String result = "";
String charXInString;
String remainString;
for (int i = 0; i < str.length(); i++) {
charXInString = str.charAt(i) + "";
remainString = str.substring(0, i)+ str.substring(i + 1, str.length());
for (String element : getAllOrder(remainString)) {
result = charXInString + element;
set.add(result);
}
}
arrResult = set.toArray(new String[set.size()]);
}else{
arrResult = new String[]{str};
}
return arrResult;
}
}
⑦ 關於全排列遞歸演算法
這個演算法，是把每一個數與末尾的數逐一交換，
k>m 說明已交換完畢，就輸出了，這是遞歸的結束條件。
要學到一定的基本功才能明白。
---------------------------------------------------------------------------
我這個程序，我也編過，放在西祠C++BUILDER論壇里。
你先要掌握，排列的方法才能看懂這個程序。
在這知道里，也答過兩次。
為了增加可理解性，我略改了一下方法，我的方法
與你的方法遞歸方向不同。
http://www.xici.net/d190786398.htm
此演算法為遞歸法顯示排列數，沒發現比這更簡單、明了的遞
歸演算法。此演算法只要練智商的作用，沒有其它實用價值，階
乘級的佔用時間、空間，數一大，堆棧很快暴了。
演算法的要點：
1.列N個數的排列，可化為N個的N-1階排列：
最末一個數是 D[n-1]，把這個位置的N個數的可能性列出，
就是每一個數 與末尾逐一交換位置，就是N種情況，每一種
情況再求N-1的全排列，就是遞歸調用了；
交換位置後，就調用自已，但必須恢復剛才的交換，以便下一次
交換；
2.當階數遞歸到1時，就直接輸出這N個數；
⑧ 求遍歷全排列的演算法
全排列的生成演算法就是對於給定的字元集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。
常見的有四種全排列演算法：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法
這里著重介紹字典序法
對給定的字元集中的字元規定了一個先後關系，在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字元的先後。
[例]字元集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
[注意] 一個全排列可看做一個字元串，字元串可有前綴、後綴。
1）生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的後綴上。
[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最後面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。
⑨ 全排列遞歸演算法
希望我的答復可以幫助你加深理解：
第一，perm函數中的條件for(int i=k;i<=m;i++)應更正為 for(int i=k;i<m;i++)
第二，你可以在核心步驟的前後列印有關變數的值，分析查看每一步的具體執行情況，這是編程調試的重要能力，要加強。
第三，以下是我提供的附件程序及運行結果（以1,2,3這個數組的全排列），可輔助分析：
1. 程序源碼=================================================
#include <stdio.h>
#include <stdlib.h>
int N,P=0;
void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void perm(int a[],int k,int m,int pk,int pm)
{
int i;
/*k為中間變數，m初始化為參與排列元素的起始坐標和終止坐標
pk,pm分別表示參與排列元素的起始坐標和終止坐標，整個遞歸過程保持不變*/
if(k==m)
{
printf("----->perm %d :\n",P/N+1);/*列印提示*/
for(i=pk;i<pm;i++)
{
printf("%d ",a[i]);
P=P+1;
}
printf("\n\n");
}
else
{
for(i=k;i<m;i++)
{
printf("a %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("b %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
perm(a,k+1,m,pk,pm);
printf("c %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("d %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
}
}
}
int main()
{
/*調節以下N值及對應數組內容，可列印對應數組對應的全排列*/
N=3;
int t[]={1,2,3};
/*調節以上N值及對應數組內容，可列印對應數組對應的全排列*/
perm(t,0,N,0,N);
printf("----->Over!\n");/*列印提示*/
system("pause");
return 0;
}
2.列印結果 ============================================================
a 0,0,1,2,3
b 0,0,1,2,3
a 1,1,1,2,3
b 1,1,1,2,3
a 2,2,1,2,3
b 2,2,1,2,3
----->perm 1 :
1 2 3
c 2,2,1,2,3
d 2,2,1,2,3
c 1,1,1,2,3
d 1,1,1,2,3
a 2,1,1,2,3
b 2,1,1,3,2
a 2,2,1,3,2
b 2,2,1,3,2
----->perm 2 :
1 3 2
c 2,2,1,3,2
d 2,2,1,3,2
c 2,1,1,3,2
d 2,1,1,2,3
c 0,0,1,2,3
d 0,0,1,2,3
a 1,0,1,2,3
b 1,0,2,1,3
a 1,1,2,1,3
b 1,1,2,1,3
a 2,2,2,1,3
b 2,2,2,1,3
----->perm 3 :
2 1 3
c 2,2,2,1,3
d 2,2,2,1,3
c 1,1,2,1,3
d 1,1,2,1,3
a 2,1,2,1,3
b 2,1,2,3,1
a 2,2,2,3,1
b 2,2,2,3,1
----->perm 4 :
2 3 1
c 2,2,2,3,1
d 2,2,2,3,1
c 2,1,2,3,1
d 2,1,2,1,3
c 1,0,2,1,3
d 1,0,1,2,3
a 2,0,1,2,3
b 2,0,3,2,1
a 1,1,3,2,1
b 1,1,3,2,1
a 2,2,3,2,1
b 2,2,3,2,1
----->perm 5 :
3 2 1
c 2,2,3,2,1
d 2,2,3,2,1
c 1,1,3,2,1
d 1,1,3,2,1
a 2,1,3,2,1
b 2,1,3,1,2
a 2,2,3,1,2
b 2,2,3,1,2
----->perm 6 :
3 1 2
c 2,2,3,1,2
d 2,2,3,1,2
c 2,1,3,1,2
d 2,1,3,2,1
c 2,0,3,2,1
d 2,0,1,2,3
----->Over!
請按任意鍵繼續. . .
⑩ 關於全排列的演算法問題
最低0.27元/天開通網路文庫會員，可在文庫查看完整內容>
原發布者:ON9V4Xr2gU9J7
全排列以及相關演算法在程序設計過程中，我們往往要對一個序列進行全排列或者對每一個排列進行分析。全排列演算法便是用於產生全排列或者逐個構造全排列的方法。當然，全排列演算法不僅僅止於全排列，對於普通的排列，或者組合的問題，也可以解決。本文主要通過對全排列以及相關演算法的介紹和講解、分析，讓讀者更好地了解這一方面的知識，主要涉及到的語言是C和C++。本文的節數：1.全排列的定義和公式：2.時間復雜度：3.列出全排列的初始思想：4.從第m個元素到第n個元素的全排列的演算法：5.全排列演算法：6.全排列的字典序：7.求下一個字典序排列演算法：8.C++STL庫中的next_permutation()函數：（#include）9.字典序的中介數，由中介數求序號：10.由中介數求排列：11.遞增進位制數法：12.遞減進位制數法：13.鄰位對換法：14.鄰位對換法全排列：15.鄰位對換法的下一個排列：16.鄰位對換法的中介數：17.組合數的字典序與生成：由於本文的，內容比較多，所以希望讀者根據自己的要求閱讀，不要一次性讀完，有些章節可以分開讀。第1節到第5節提供了全排列的概念和一個初始的演算法。第6節到第8節主要講述了字典序的全排列演算法。第9到第10節講了有關字典序中中介數的概念。第11到第12節主要介紹了不同的中介數方法，僅供擴展用。第13節到15節介紹了鄰位對換法的全排的有關知識。16節講了有關鄰位對換法的中介數，僅供參考。第17節講了