Skip to content

Instantly share code, notes, and snippets.

@vo
Created April 1, 2010 07:43
Show Gist options
  • Save vo/351518 to your computer and use it in GitHub Desktop.
Save vo/351518 to your computer and use it in GitHub Desktop.
getting permutations
//
// An example of how to generate permutations
// using STL algorithms library
//
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
const int N = 8;
int A[] = { 1, 5, 6, 2, 7, 1, 2, 8 };
sort(A, A+N);
do {
for(int i = 0; i < N; i++)
cout << A[i] << " ";
cout << endl;
} while (next_permutation (A,A+N));
return 0;
}
//
// An example of how to generate permutations
// using Heap's algorithm
//
#include <cstdio>
using namespace std;
// an array of stuff to permute
const int N = 8;
int A[N] = { 1, 5, 6, 2, 7, 1, 2, 8 };
void print() {
for(int i=0; i<N; i++)
printf("%d ", A[i]);
printf("\n");
}
int main(int argc, char * argv[])
{
// make an idx array filled with zero
int idx[N];
for(int i=0; i < N; i++)
idx[i] = 0;
print();
// heap's algorithm, iterative version
for (int i=1; i < N;) {
if (idx[i] < i) {
int swap = i % 2 * idx[i];
int tmp = A[swap];
A[swap] = A[i];
A[i] = tmp;
print();
idx[i]++;
i = 1;
} else {
idx[i++] = 0;
}
}
return 0;
}
//
// An example of how to generate permutations
// using Heap's algorithm (Java version)
//
import java.util.Arrays;
public class Heap {
private static int A[] = { 1, 5, 6, 2, 7 };
public static void main(String[] args) {
// make idx array with zeros
int[] idx = new int[A.length];
Arrays.fill(idx, 0);
System.out.println(Arrays.toString(A));
// heap's algorithm, iterative
for (int i = 1; i < A.length;) {
if (idx[i] < i) {
int swap = i % 2 * idx[i];
int tmp = A[swap];
A[swap] = A[i];
A[i] = tmp;
System.out.println(Arrays.toString(A));
idx[i]++;
i = 1;
} else {
idx[i++] = 0;
}
}
}
}
#
# An example of how to generate permutations
# using Heap's algorithm (Python version)
#
def permute(L):
N = len(L)
idx = [0 for i in range(N)]
result = [L]
i = 1
while i < N:
if idx[i] < i:
L = list(L)
swap = i % 2 * idx[i]
L[swap], L[i] = L[i], L[swap]
result.append(L)
idx[i] += 1
i = 1
else:
idx[i] = 0
i += 1
return result
#
# How to generate a list of permutations using Python standard library
#
import itertools
itertools.permutations(lis)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment