possibleset.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 297 行
HTM
297 行
<!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}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。<br>
<h2>解法</h2>
如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例如： <br>
<table border="1" width="50%">
<tbody>
<tr>
<td align="left" valign="top"><small>000 </small></td>
<td align="left" valign="top"><small>{} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>001 </small></td>
<td align="left" valign="top"><small>{3} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>010 </small></td>
<td align="left" valign="top"><small>{2} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>011 </small></td>
<td align="left" valign="top"><small>{2,3} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>100 </small></td>
<td align="left" valign="top"><small>{1} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>101 </small></td>
<td align="left" valign="top"><small>{1,3} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>110 </small></td>
<td align="left" valign="top"><small>{1,2} </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>111 </small></td>
<td align="left" valign="top"><small>{1,2,3} </small></td>
</tr>
</tbody>
</table>
<br>
了解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned型别加上&位元运算来产生，这边则是使用阵列搜
寻，首先阵列内容全为0，找第一个1，在还没找到之前将走访过的内容变为0，而第一个找到的0则变为
1，如此重复直到所有的阵列元素都变为1为止，例如：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">000 => 100 => 010 => 110 => 001 => 101 => 011 => 111</span><br>
</div>
<br>
如果要产生字典顺序，例如若有4个元素，则：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{1,2,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{1,3} => {1,3,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{1,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{2} => {2,3} => {2,3,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{2,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{3} => {3,4} =></span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{4}</span><br>
</div>
<br>
简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而倒数第二个元素是m的话，例如：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">{a b c d e n}</span><br>
</div>
<br>
则下一个集合就是{a b c d e+1}，再依序加入后续的元素。<br>
<br>
例如有四个元素，而当产生{1 2 3 4}集合时，则下一个集合就是{1 2 3+1}，也就是{1 2
4}，由于最后一个元素还是4，所以下一个集合就是{1 2+1}，也就是{1 3}，接下来再加入后续元素4，也就是{1 3
4}，由于又遇到元素4，所以下一个集合是{1 3+1}，也就是{1 4}。<br>
<h2> 实作</h2>
<ul>
<li> C（无字典顺序）
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>#define MAXSIZE 20 <br><br>int main(void) { <br> char digit[MAXSIZE]; <br> int i, j; <br> int n; <br><br> printf("输入集合个数："); <br> scanf("%d", &n); <br><br> for(i = 0; i < n; i++) <br> digit[i] = '0'; <br><br> printf("\n{}"); // 空集合 <br><br> while(1) { <br> // 找第一个0，并将找到前所经过的元素变为0 <br> for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++); <br><br> if(i == n) // 找不到0 <br> break; <br> else // 将第一个找到的0变为1 <br> digit[i] = '1'; <br><br> // 找第一个1，并记录对应位置 <br> for(i = 0; i < n && digit[i] == '0'; i++); <br><br> printf("\n{%d", i+1); <br> <br> for(j = i + 1; j < n; j++) <br> if(digit[j] == '1') <br> printf(",%d", j + 1); <br><br> printf("}"); <br> } <br> <br> printf("\n"); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> C（字典顺序）
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>#define MAXSIZE 20 <br><br>int main(void) { <br> int set[MAXSIZE]; <br> int i, n, position = 0; <br><br> printf("输入集合个数："); <br> scanf("%d", &n); <br> printf("\n{}"); <br> set[position] = 1; <br><br> while(1) { <br> printf("\n{%d", set[0]); // 印第一个数 <br> for(i = 1; i <= position; i++) <br> printf(",%d", set[i]); <br> printf("}"); <br><br> if(set[position] < n) { // 递增集合个数 <br> set[position+1] = set[position] + 1; <br> position++; <br> } <br> else if(position != 0) { // 如果不是第一个位置 <br> position--; // 倒退 <br> set[position]++; // 下一个集合尾数 <br> } <br> else // 已倒退至第一个位置 <br> break; <br> } <br><br> printf("\n"); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> Java（无字典顺序）
</li>
</ul>
<pre>public class PossibleSet {<br> public static void main(String[] args) {<br> char[] digit = new char[4]; <br><br> for(int i = 0; i < digit.length; i++) <br> digit[i] = '0'; <br><br> System.out.println("{}"); // 空集合 <br><br> while(true) { <br> // 找第一个0，并将找到前所经过的元素变为0<br> int i;<br> for(i = 0; i < digit.length && digit[i] == '1'; <br> digit[i] = '0', i++); <br><br> if(i == digit.length) // 找不到0 <br> break; <br> else // 将第一个找到的0变为1 <br> digit[i] = '1'; <br><br> // 找第一个1，并记录对应位置 <br> for(i = 0; i < digit.length && digit[i] == '0'; i++); <br><br> System.out.print("{" + (i+1)); <br> <br> for(int j = i + 1; j < digit.length; j++) <br> if(digit[j] == '1') <br> System.out.print(", " + (j + 1)); <br><br> System.out.println("}"); <br> } <br> }<br>} <br></pre>
<br>
<ul>
<li> Java（字典顺序）
</li>
</ul>
<pre>public class PossibleSet {<br> public static void main(String[] args) {<br> int[] set = new int[4]; <br> int i, n, position = 0; <br><br> set[position] = 1; <br><br> while(true) { <br> System.out.print("{" + set[0]); // 印第一个数 <br> for(i = 1; i <= position; i++) <br> System.out.print("," + set[i]); <br> System.out.print("}"); <br><br> if(set[position] < set.length) { // 递增集合个数 <br> set[position+1] = set[position] + 1; <br> position++; <br> } <br> else if(position != 0) { // 如果不是第一个位置 <br> position--; // 倒退 <br> set[position]++; // 下一个集合尾数 <br> } <br> else // 已倒退至第一个位置 <br> break; <br> } <br><br> System.out.println(); <br> }<br>}</pre>
<br>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?