📄 permutation.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>排列组合</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 排列组合</a></h1>
<h2>说明</h2>
将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。<br>
<h2>解法</h2>
可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4
[1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold;">1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递回处理</span><br style="font-weight: bold;">
<span style="font-weight: bold;">2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递回处理</span><br style="font-weight: bold;">
<span style="font-weight: bold;">3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递回处理</span><br style="font-weight: bold;">
<span style="font-weight: bold;">4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递回处理 </span><br>
</div>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#define N 4 <br><br>void perm(int*, int); <br><br>int main(void) { <br> int num[N+1], i; <br><br> for(i = 1; i <= N; i++) <br> num[i] = i; <br><br> perm(num, 1); <br><br> return 0; <br>} <br><br>void perm(int* num, int i) { <br> int j, k, tmp; <br><br> if(i < N) { <br> for(j = i; j <= N; j++) { <br> tmp = num[j]; <br> // 旋转该区段最右边数字至最左边 <br> for(k = j; k > i; k--) <br> num[k] = num[k-1]; <br> num[i] = tmp; <br><br> perm(num, i+1); <br><br> // 还原 <br> for(k = i; k < j; k++) <br> num[k] = num[k+1]; <br> num[j] = tmp; <br> } <br> } <br> else { // 显示此次排列 <br> for(j = 1; j <= N; j++) <br> printf("%d ", num[j]); <br> printf("\n"); <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class Permutation {<br> public static void perm(int[] num, int i) {<br><br> if(i < num.length - 1) { <br> for(int j = i; j <= num.length - 1; j++) { <br> int tmp = num[j]; <br> // 旋转该区段最右边数字至最左边 <br> for(int k = j; k > i; k--) <br> num[k] = num[k-1]; <br> num[i] = tmp; <br><br> perm(num, i+1); <br><br> // 还原 <br> for(int k = i; k < j; k++) <br> num[k] = num[k+1]; <br> num[j] = tmp; <br> } <br> } <br> else { // 显示此次排列 <br> for(int j = 1; j <= num.length - 1; j++) <br> System.out.print(num[j] + " "); <br> System.out.println(); <br> } <br> }<br><br> public static void main(String[] args) {<br> int[] num = new int[4+1]; <br><br> for(int i = 1; i <= num.length - 1; i++) <br> num[i] = i; <br><br> perm(num, 1); <br> }<br>}<br></pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -