Print all permutations of n distinct elements.
// Permutaion.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
void Swap(vector<char>& vec, int posA, int posB)
{
char temp = vec[posA];
vec[posA] = vec[posB];
vec[posB] = temp;
}
void Permutation(vector<char>& vec, int count)
{
if(vec.size() == 0){
cout << "Empty character set" << endl;
}
else if(vec.size() == 1){
cout << vec[0] << endl;
return;
}
if(count == vec.size()){
copy(vec.begin(), vec.end(), ostream_iterator<char>(cout, " "));
cout << endl;
return;
}
for(int i = count; i < vec.size(); i ++){
Swap(vec, count, i);
Permutation(vec, count + 1);
Swap(vec, count, i);
}
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 5; ++ i){
vector<char> vec;
for(int j = 0; j < i; ++j){
vec.push_back('A' + j);
}
cout << "Characters in set: " << endl;
copy(vec.begin(), vec.end(), ostream_iterator<char>(cout, " "));
cout << endl << "Permuations: " << endl;
Permutation(vec, 0);
}
return 0;
}
Output
Characters in set:
Permuations:
Empty character set
Characters in set:
A
Permuations:
A
Characters in set:
A B
Permuations:
A B
B A
Characters in set:
A B C
Permuations:
A B C
A C B
B A C
B C A
C B A
C A B
Characters in set:
A B C D
Permuations:
A B C D
A B D C
A C B D
A C D B
A D C B
A D B C
B A C D
B A D C
B C A D
B C D A
B D C A
B D A C
C B A D
C B D A
C A B D
C A D B
C D A B
C D B A
D B C A
D B A C
D C B A
D C A B
D A C B
D A B C
Press any key to continue . . .
class Permutation {
public static void main(String[] argument) {
int[] list = { 1, 2, 3, 4 };
Permutation.Perm(list, 0);
}
private static void Swap(int[] list, int i, int j) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
public static void Perm(int[] list, int preceding) {
int length = list.length;
if (preceding == length - 1) {
for (int i = 0; i < list.length; ++i)
System.out.print(list[i] + " ");
System.out.println();
} else {
for (int i = preceding; i < length; ++i) {
Swap(list, preceding, i);
Perm(list, preceding + 1);
Swap(list, preceding, i);
}
}
}
}
Output
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3