FilesExpand file tree

 master

/

permutations.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

112 lines (101 loc) · 2.48 KB

 master

/

permutations.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

112 lines (101 loc) · 2.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

// Source : https://oj.leetcode.com/problems/permutations/

// Author : Hao Chen

// Date : 2014-06-21

/**********************************************************************************

*

* Given a collection of numbers, return all possible permutations.

*

* For example,

* [1,2,3] have the following permutations:

* [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

*

*

**********************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <vector>

using namespace std;

/*

{ 1 2 3 }

{ 2 1 3 }

{ 3 2 1 }

{ 1 3 2 }

{ 2 3 1 }

{ 3 1 2 }

*/

/*

* The algroithm - Take each element in array to the first place.

*

* For example:

*

* 0) initalization

*

* pos = 0

* [1, 2, 3]

*

* 1) take each element into the first place,

*

* pos = 1

* [1, 2, 3] ==> [2, 1, 3] , [3, 1, 2]

*

* then we have total 3 answers

* [1, 2, 3], [2, 1, 3] , [3, 1, 2]

*

* 2) take each element into the "first place" -- pos

*

* pos = 2

* [1, 2, 3] ==> [1, 3, 2]

* [2, 1, 3] ==> [2, 3, 1]

* [3, 1, 2] ==> [3, 2, 1]

*

* then we have total 6 answers

* [1, 2, 3], [2, 1, 3] , [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]

*

* 3) pos = 3 which greater than length of array, return.

*

*/

vector<vector<int> > permute(vector<int> &num) {

vector<vector<int> > vv;

vv.push_back(num);

if (num.size() <2){

return vv;

}

int pos=0;

while(pos<num.size()-1){

int size = vv.size();

for(int i=0; i<size; i++){

//take each number to the first place

for (int j=pos+1; j<vv[i].size(); j++) {

vector<int> v = vv[i];

int t = v[j];

v[j] = v[pos];

v[pos] = t;

vv.push_back(v);

}

}

pos++;

}

return vv;

}

int main(int argc, char** argv)

{

int n = 3;

if (argc>1){

n = atoi(argv[1]);

}

vector<int> v;

for (int i=0; i<n; i++) {

v.push_back(i+1);

}

vector<vector<int> > vv;

vv = permute(v);

for(int i=0; i<vv.size(); i++) {

cout << "{ ";

for(int j=0; j<vv[i].size(); j++){

cout << vv[i][j] << " ";

}

cout << "}" <<endl;

}

return 0;

}