491
D的小L---全排列
D的小L
時間限製：4000 ms | 內存限製：65535 KB
難度：2
描述
一天TC的匡匡找ACM的小L玩三國殺，但是這會小L忙著哩，不想和匡匡玩但又怕匡匡生氣，這時小L給匡匡出了個題目想難倒匡匡(小L很D吧)，有一個數n(0<n<10),寫出1到n的全排列，這時匡匡有點囧了，，，聰明的你能幫匡匡解圍嗎？
輸入
第一行輸入一個數N（0<N<10）,表示有N組測試數據。後麵的N行輸入多組輸入數據，每組輸入數據都是一個整數x(0<x<10)
輸出
按特定順序輸出所有組合。
特定順序：每一個組合中的值從小到大排列，組合之間按字典序排列。
樣例輸入
2
2
3
樣例輸出
12
21
123
132
213
231
312
321
查看代碼---運行號：253085----結果：Accepted
運行時間：2012-10-07 20:48:25 | 運行人:huangyibiao
view sourceprint?
01.#include <iostream>
02.
03.usingnamespacestd;
04.
05.voidPrintElems(int*elem, int size)
06.{
07.for(inti = 1; i <= size; i++)
08.cout << elem[i];
09.cout << endl;
10.}
11.
12.voidSwap(int&first, int &second)
13.{
14.inttmp = first;
15.first = second;
16.second = tmp;
17.}
18.
19.voidReverse(int*elem, int leftIndex,int size)
20.{
21.for(inti = leftIndex, j = size; j >= i; i++, j--)
22.{
23.Swap(elem[i], elem[j]);
24.}
25.
26.}
27.
28.boolNotFinished(int*elem, int size)
29.{
30.
31.//從右往左尋找第一個相鄰元素中左邊元素小於右邊的元素的位置
32.intleftIndex = -1;
33.for(inti = size; i >= 2; i--)//0號不用
34.{
35.if(elem[i-1] < elem[i])
36.{
37.leftIndex = i-1;
38.break;
39.}
40.}//*******************************************************
41.if(leftIndex == -1)//找不到了，說明已經全部排完
42.{
43.returnfalse;
44.}
45.
46.//從右往左尋找右邊的元素中大於前麵已經找到的元素的最小元素的位置
47.intrightIndex = -1;
48.for(inti = size; i >= leftIndex; i--)
49.{
50.if(elem[i] > elem[leftIndex])
51.{
52.rightIndex = i;
53.break;
54.}
55.}
56.//交換這兩個元素
57.Swap(elem[leftIndex], elem[rightIndex]);
58.
59.Reverse(elem, leftIndex+1, size);
60.
61.returntrue;
62.}
63.
64.intmain()
65.{
66.intsample;
67.cin >> sample;
68.
69.while(sample--)
70.{
71.intx;
72.cin >> x;
73.int*elem =new int[x+1];
74.
75.for(inti = 0; i <= x; i++)
76.elem[i] = i;
77.while(true)
78.{
79.PrintElems(elem, x);
80.if(!NotFinished(elem, x))
81.break;
82.}
83. delete []elem;
84.}
85.return0;
86.}
最後更新：2017-04-02 15:14:56