排列组合的输出，求时间效率更高的方法
下面的代码如何改进能使时间复杂度更低呢？常数级别的优化也行
#include <iostream>性能优化
using std::cout;
using std::endl;
void H(char* a,int n,int k); //有重复的组合
void C(char* a, int n, int k); //无重复的组合
void P(char* a, int n); //字典序全排列
void Perm(char* a,int k,int m); //递归分治全排列
void Perm(char* a,int n); //非递归全排列
void Swap(char &a, char &b); //交换数组的两个元素值
int main(int argc,char* argv[]) {
char a[] = "0123";
int n = sizeof(a) / sizeof(a[0]) - 1;
P(a, n);
cout << endl;
C(a, n, 3);
cout << endl;
H(a, n, 3);
cout << endl;
Perm(a, n);
cout << endl;
Perm(a, n, 0);
cout << endl ;
return 0;
}
void H(char* a,int n,int k) {
int nn = n + k - 1;
int kk = n - 1;
int* b = new int[kk + 3];
int i;
for (i = 0; i < n + 2; ++i) {
b[i] = i - 1;
}
b[n] = nn;
while (-1 == b[0]) {
for (i = 1; i < n + 1; ++i) {
cout << b[i] - b[i - 1] - 1 << "(" << i - 1 << "), ";
}
cout << endl;
++b[kk];
if (b[kk] >= nn) {
for (i = kk - 1; i >= 0; --i) {
if (b[i] + 1 < nn - kk + i) {
++b[i];
for (int j = i + 1; j <= kk; ++j) {
b[j] = b[j - 1] + 1;
}
break;
}
}
}
}
delete [] b;
}
void C(char* a, int n, int k) {
int* b = new int[k + 1];
int i,j;
for (i = 0; i <= k; ++i) {
b[i] = i - 1;
}
while (-1 == b[0]) {
for (i = 1; i <= k; ++i) {
cout << a[b[i]];
}
cout << endl;
++b[k];
if (b[k] >= n) {
for (i = k - 1; i >= 0; --i) {
if (b[i] + 1 < n - k + i) {
++b[i];
for (int j = i + 1; j <= k; ++j) {
b[j] = b[j - 1] + 1;
}
break;
}
}
}
}
delete [] b;
}
void P(char* a, int n) { //要求先将a字符数组按升序排列
int* b = new int[256];
int i,j,k;
char* aCopy = new char[n + 1];
strcpy_s(aCopy,n+1,a);
memset(b,0,256 * sizeof(int));
while (true) {
for (k = 0; k < n; ++k) {
cout << aCopy[k];
}
cout << endl;
for (i = n - 2; i >= 0; --i) {
if (aCopy[i] < aCopy[i + 1]) {
for (j = n - 1; j > i; --j) {
if (aCopy[j] > aCopy[i]) {
Swap(aCopy[i],aCopy[j]);
memset(b,0,256 * sizeof(int));
for (k = i + 1; k < n; ++k) {
++b[aCopy[k]];
}
int l = i + 1;
for (k = 0; k < 256; ++k) {
if (b[k] == 1) {
aCopy[l++] = k;
}
}
goto done;
}
}
}
}
done:
if (i == -1) break;
}
delete [] b;
delete [] aCopy;
}
void Perm(char* a,int n,int k) {
if(n - 1 == k) {
for(int i = 0; i < n; ++i) {
cout << a[i];
}
cout << endl;
} else {
for(int i = k; i < n; i++) {
Swap(a[k], a[i]);
Perm(a, n, k + 1);
Swap(a[k], a[i]);
}
}
}
void Perm(char* a,int n) {
int* b = new int[n + 1];
char* aCopy = new char[n + 1];
int i;
strcpy_s(aCopy,n+1,a);
for (int i = 0; i < n; ++i) {
b[i] = i;
}
while (true) {
strcpy_s(aCopy,n+1,a);
for (i = 0; i < n; ++i) {
Swap(aCopy[i],aCopy[b[i]]);
}
for (i = 0; i < n; ++i) {
cout << aCopy[i];
}
cout << endl;
++b[0];
for (i = 0; i < n; ++i) {
if (b[i] > n - 1) {
++b[i + 1];
b[i] = i;
} else {
break;
}
}
if (i == n) {
break;
}
}
delete [] b;
delete [] aCopy;
}
void Swap(char &a, char &b) {
char t = a;
a = b;
b = t;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int m;//记录字符串长度
int n;//记录字符串中的字符种类数
char map[256];//记录是哪几种字符
int count[256];//记录每种字符有多少个
int stack[1000];//递归用的栈，并记录当前生成的排列
void Make_Map(char *str) {//统计字符串的相关信息
int s[256];
int i;
memset(s,0,sizeof(s));
memset(count,0,sizeof(count));
m=strlen(str);
while(*str) {
s[*str]++;
str++;
}
n=0;
for (i=0;i<256;i++)
if (s[i]) {
map[n]=i;
count[n]=s[i];
n++;
}
}
void Find(int depth) {//递归式回溯法生成全排列
if (depth==m) {
int i;
for (i=0;i<depth;i++) putchar(map[stack[i]]);
putchar('\n');
} else {
int i;
for (i=0;i<n;i++)
if (count[i]) {
stack[depth]=i;
count[i]--;
Find(depth+1);
count[i]++;
}
}
}
void main(int argc,char**argv) {
if (argc<2) {
printf("%s 要产生全排列的字符串\n",argv[0]);
return;
}
Make_Map(argv[1]);
Find(0);
}
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 26
int comb[MAX_NUM];
int c1,c2;
void combination(int m,int n) {
int i,j;
for (i=m;i>=n;i--) {
comb[n]=i; /* 选择当前的“头”元素 */
if (n>1) {
combination(i-1,n-1); /* 进入下一次更小的组合问题 */
} else { /* 满了需要的组合数，输出 */
for (j=comb[0];j>0;j--) printf("%c",'A'+c1-comb[j]);
printf("\n");
}
}
return;
}
int main(int argc,char **argv) {
if (argc<3) {
printf("%s 组合下标 组合上标\n",argv[0]);
return 1;
}
c1=atoi(argv[1]);
if (c1<1
[解决办法]
MAX_NUM<c1) {
printf("1<=组合下标<=%d\n",MAX_NUM);
return 2;
}
c2=atoi(argv[2]);
if (c2<1
[解决办法]
c1<c2) {
printf("1<=组合上标<=组合下标\n");
return 3;
}
comb[0]=c2;
combination(c1,c2);
return 0;
}
使用命令重定向操作符可以使用重定向操作符将命令输入和输出数据流从默认位置重定
向到不同的位置。输入或输出数据流的位置即为句柄。
下表将列出可用的句柄。
句柄 句柄的数字代号 描述
STDIN 0 键盘输入
STDOUT 1 输出到命令提示符窗口
STDERR 2 错误输出到命令提示符窗口
UNDEFINED 3-9 这些句柄由应用程序单独定义，并且是各个工具特定的。
数字 0 到 9 代表前 10 个句柄。可以使用命令 Cmd.exe 运行程序并将该程序前 10 个
句柄中的任何一个重定向。要指定想使用的句柄，可在重定向操作符前面键入该句柄的
数字。如果未定义句柄，则默认的 < 重定向输入操作符是 0，而默认的 > 重定向输出
操作符是 1。键入 > 或 < 操作符之后，必须指定要读取或写入数据的位置。可以指定
文件名或另一个现有的句柄。
要指定重定向到现有句柄，请使用与 (&) 字符，后面接要重定向的句柄号
（例如 &句柄#）。例如，下面的命令可以将句柄 2（即 STDERR）重定向到
句柄 1（即 STDOUT）：
2>&1
下表列出了可用于将输入和输出数据流进行重定向的操作符。
重定向操作符 描述
> 将命令输出写入到文件或设备（例如打印机）中，而不是写在命令提示符窗口或句柄中。
< 从文件中而不是从键盘或句柄中读入命令输入。
>> 将命令输出添加到文件末尾而不删除文件中的信息。
>& 将一个句柄的输出写入到另一个句柄的输入中。
<& 从一个句柄读取输入并将其写入到另一个句柄输出中。
[解决办法]
从一个命令中读取输出并将其写入另一个命令的输入中。也称作管道。
默认情况下，可以从键盘将命令输入（即 STDIN 句柄）发送到 Cmd.exe，然后由
Cmd.exe 将命令输出（即 STDOUT 句柄）发送到命令提示符窗口。
重定向输入 (<)
要将键盘输入重定向到文件或设备，请使用 < 操作符。例如，要从 File.txt 获取
sort 命令的输入，请键入：
sort<file.txt
File.txt 的内容将以字母顺序列表的方式显示在命令提示符窗口中。
< 操作符可以打开具有只读访问的指定文件名。所以，不能使用该操作符向文件中写入
信息。例如，如果以 <&2 启动程序，则所有试图读取句柄 0 的操作都将失败，因为句
柄 2 最初是以只写访问打开的。
注意
0 是 < 重定向输入操作符的默认句柄。
重定向输出 (>)
几乎所有的命令都将输出发送到命令提示符窗口。即使将输出发送到驱动器或打印机的
命令也会在命令提示符窗口显示消息和提示。
要将输出从命令提示符窗口重定向到文件或设备，请使用 > 操作符。可以在许多命令中
使用该操作符。例如，要将 dir 输出重定向到 Dirlist.txt，请键入：
dir>dirlist.txt
如果 Dirlist.txt 不存在，Cmd.exe 将创建该文件。如果 Dirlist.txt 存在，Cmd.exe
将使用 dir 命令的输出替换文件中的信息。
要运行 netsh routing dump 命令，然后将输出发送到 Route.cfg，请键入：
netsh routing dump>c:\route.cfg
> 操作符可以打开具有只写访问属性的指定文件。所以，不能使用该操作符读取文件。
例如，如果使用重定向 >&0 启动程序，则所有试图写入句柄 1 的操作都将失败，因为
句柄 0 最初是以只读访问打开的。
注意
1 是 > 重定向输出操作符的默认句柄。
复制句柄
重定向操作符 & 可以将输出或输入从一个指定句柄复制到另一个指定的句柄。例如，
要将 dir 输出发送到 File.txt 并将错误输出发送到 File.txt，请键入：
dir>c:\file.txt 2>&1
复制句柄时，可以复制该句柄原状态的所有特性。例如，如果一个句柄具有只写访问的
属性，则该句柄的所有副本都具有只写访问属性。不能将一个具有只读访问属性的句柄
复制到另一个具有只写访问属性的句柄。
使用 & 操作符重定向输入和副本
要将重定向输入操作符 (<) 与复制操作符 (&) 一起使用，指定的文件必须已经存在。
如果输入文件存在，Cmd.exe 将以只读方式打开该文件，然后将文件中包含的字符作为
输入发送到此命令（如同从键盘输入一样）。如果指定了句柄，Cmd.exe 将指定的句柄
复制到系统现有的句柄中。
例如，要以句柄 0 输入读取（即 STDIN）的方式打开 File.txt，请键入：
<file.txt
要打开 File.txt，并在内容排序后将输出发送到命令提示符窗口（即 STDOUT），请键入：
sort<file.txt
要查找 File.txt，然后将句柄 1（即 STDOUT）和句柄 2（即 STDERR）重定向到
Search.txt，请键入：
findfile file.txt>search.txt 2<&1
要以句柄 0 输入读取（即 STDIN）的方式复制用户定义句柄 3，请键入：
<&3
使用 & 操作符重定向输出和复制
如果将输出重定向到文件且指定了现有的文件名，Cmd.exe 将以只写方式打开文件并覆
盖该文件内容。如果指定了句柄，Cmd.exe 将文件复制到现有句柄中。
要将用户定义句柄 3 复制到句柄 1，请键入：
>&3
要将包括句柄 2（即 STDERR）的所有输出从 ipconfig 命令重定向到
句柄 1（即 STDOUT），然后将输出重定向到 Output.log，请键入：
ipconfig.exe>>output.log 2>&1
使用 >> 重定向操作符追加输出
要从命令中将输出添加到文件末尾而不丢失文件中已存在的任何信息，请使用两个连续
的大于号（即 >>）。例如，下面的命令可以将由 dir 命令生成的目录列表追加到
Dirlist.txt 文件：
dir>>dirlist.txt
要将 netstat 命令的输出追加到 Tcpinfo.txt 的末尾，请键入：
netstat>>tcpinfo.txt
使用管道操作符 (
[解决办法]
)
管道操作符 (
[解决办法]
) 可以提取一个命令的输出（默认情况下是 STDOUT），然后将其导入另
一个命令的输入中（默认情况下是 STDIN）。例如，下面的命令将对目录分类：
dir
[解决办法]
sort
在本例中，将同时启动两个命令，但随后 sort 命令会暂停，直到它接收到 dir 命令
的输出为止。sort 命令使用 dir 命令的输出作为输入，然后将输出发送到
句柄 1（即 STDOUT）。
合并带重定向操作符的命令
可以通过合并带有其他命令和文件名的筛选器命令创建自定义命令。例如，可以使用以
下命令存储包含“LOG”字符串的文件名:
dir /b
[解决办法]
find "LOG" > loglist.txt
dir 命令的输出通过 find 筛选器命令发送。包含字符串 "LOG" 的文件名作为文件名
列表（例如，NetshConfig.log、Logdat.svd 和 Mylog.bat）存储在文件
Loglist.txt 中。
要在相同命令中使用多个筛选器，请使用管道 (
[解决办法]
) 分隔筛选器。例如，下面的命令将
搜索 C 盘上的每个目录以查找包含 "LOG" 字符串的文件名，并且在命令提示符窗口中
每次显示一屏：
dir c:\ /s /b
[解决办法]
find "LOG"
[解决办法]
more
利用管道 (
[解决办法]
) 可以将 Cmd.exe 导向为通过 find 筛选器命令发送 dir 命令输出。
find 命令只选择包含字符串 "LOG" 的文件名。more 命令可以显示由 find 命令选择
的文件名（在命令提示符窗口中每次显示一屏）。有关筛选器命令的详细信息，请参阅
使用筛选器。
