How to Generate All Permutations of an Array in Sorted Order

How do I generate all permutations of a list?

Use itertools.permutations from the standard library:

import itertools
list(itertools.permutations([1, 2, 3]))

Adapted from here is a demonstration of how itertools.permutations might be implemented:

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

And another, based on itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Permutation of array

If you're using C++, you can use std::next_permutation from the <algorithm> header file:

int a[] = {3,4,6,2,1};
int size = sizeof(a)/sizeof(a[0]);
std::sort(a, a+size);
do {
  // print a's elements
} while(std::next_permutation(a, a+size));

Algorithm to generate all possible permutations of a list?

Basically, for each item from left to right, all the permutations of the remaining items are generated (and each one is added with the current elements). This can be done recursively (or iteratively if you like pain) until the last item is reached at which point there is only one possible order.

So with the list [1,2,3,4] all the permutations that start with 1 are generated, then all the permutations that start with 2, then 3 then 4.

This effectively reduces the problem from one of finding permutations of a list of four items to a list of three items. After reducing to 2 and then 1 item lists, all of them will be found.

Example showing process permutations using 3 coloured balls:

Red, green and blue coloured balls ordered permutations image (from https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)

Print the permutations of integer array in non increasing order

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int totaldigits=0;
int x[10000000];
int countx=0;
int finddigits(int num)
{
    int counter=0;
    while(num!=0)
    {
        num=num/10;
        counter++;
    }
    return counter;
}
int arrdigits(int *a,int size)
{
    int count=0;
    for(int i=0;i<=size;i++)
    {
    count+=finddigits(a[i]);
    }
    return count;
}
int findval(int n)
{
totaldigits-=finddigits(n);
return(pow(10,totaldigits)*n);
}
void findnum(int *a,int size)
{
    x[countx]=0;
    int n=0;
    for(int i=0;i<=size;i++)
    {
    n+=findval(a[i]);
    }
    x[countx]=n;
    countx++;
}
void swap(int *a,int *b)
{
int *temp;
*temp=*a;
*a=*b;
*b=*temp;
}
void permute(int *arr,int start,int end)
{
if(start==end)
{
totaldigits=arrdigits(arr,end);
findnum(arr,end);
}
else
{
    for(int j=start;j<=end;j++)
    {
        swap(arr[start],arr[j]);
        permute(arr,start+1,end);
        swap(arr[start],arr[j]);  //BACKTRACK
    }
}
}
int main()
{
int a[]={12,4,66,8,9};
totaldigits=arrdigits(a,4);
permute(a,0,4);
sort(x,x+countx);
for(int i=countx-1;i>=0;i--)
fprintf(stdout,"%ld\n",x[i]);
system("pause");
return 0;
}

Number of sorted elements (permutations), in all possible permutations of a list

Say your array is size n and the repetitions are r1, r2, ..., rk, so that sum(ri) = n. Then the answer is the product of the factorials of the repetitions.

e.g., for arr = [5, 5, 4, 4, 2, 1], we get r = [2, 2, 1, 1], and an answer of 2! * 2! * 1! * 1! = 4

Print out all permutations of an Array

Creating (or printing) the permutations of an array is much easier done as a combination of recursively and iteratively than purely iteratively. There are surely iterative ways to do it, but it is particularly simple with a combination. Specifically, note that there are by definition N! permutations of a length N array - N choices for the first slot, N-1 choices for the 2nd, etc etc. So, we can break an algorithm down into two steps for each index i in the array.

Select an element in the sub-array arr[i....end] to be the ith element of the array. Swap that element with the element currently at arr[i].
Recursively permute arr[i+1...end].

We note that this will run in O(N!), as on the 1st call N sub calls will be made, each of which will make N-1 sub calls, etc etc. Moreover, every element will end up being in every position, and so long as only swaps are made no element will ever be duplicated.

public static void permute(int[] arr){
    permuteHelper(arr, 0);
}

private static void permuteHelper(int[] arr, int index){
    if(index >= arr.length - 1){ //If we are at the last element - nothing left to permute
        //System.out.println(Arrays.toString(arr));
        //Print the array
        System.out.print("[");
        for(int i = 0; i < arr.length - 1; i++){
            System.out.print(arr[i] + ", ");
        }
        if(arr.length > 0) 
            System.out.print(arr[arr.length - 1]);
        System.out.println("]");
        return;
    }

    for(int i = index; i < arr.length; i++){ //For each index in the sub array arr[index...end]

        //Swap the elements at indices index and i
        int t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;

        //Recurse on the sub array arr[index+1...end]
        permuteHelper(arr, index+1);

        //Swap the elements back
        t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;
    }
}

Sample input, output:

public static void main(String[] args) {
    permute(new int[]{1,2,3,4});
}

[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]

How can I generate all permutations of an array in Perl?

From perlfaq4: "How do I permute N elements of a list?":

Use the List::Permutor module on CPAN. If the list is actually an array, try the Algorithm::Permute module (also on CPAN). It's written in XS code and is very efficient:

use Algorithm::Permute;

my @array = 'a'..'d';
my $p_iterator = Algorithm::Permute->new ( \@array );

while (my @perm = $p_iterator->next) {
   print "next permutation: (@perm)\n";
}

For even faster execution, you could do:

use Algorithm::Permute;

my @array = 'a'..'d';

Algorithm::Permute::permute {
    print "next permutation: (@array)\n";
} @array;

Here's a little program that generates all permutations of all the words on each line of input. The algorithm embodied in the permute() function is discussed in Volume 4 (still unpublished) of Knuth's The Art of Computer Programming and will work on any list:

#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
    my $code = shift;
    my @idx = 0..$#_;
    while ( $code->(@_[@idx]) ) {
        my $p = $#idx;
        --$p while $idx[$p-1] > $idx[$p];
        my $q = $p or return;
        push @idx, reverse splice @idx, $p;
        ++$q while $idx[$p-1] > $idx[$q];
        @idx[$p-1,$q]=@idx[$q,$p-1];
    }
}

permute { print "@_\n" } split;

The Algorithm::Loops module also provides the NextPermute and NextPermuteNum functions which efficiently find all unique permutations of an array, even if it contains duplicate values, modifying it in-place: if its elements are in reverse-sorted order then the array is reversed, making it sorted, and it returns false; otherwise the next permutation is returned.

NextPermute uses string order and NextPermuteNum numeric order, so you can enumerate all the permutations of 0..9 like this:

use Algorithm::Loops qw(NextPermuteNum);

my @list= 0..9;
do { print "@list\n" } while NextPermuteNum @list;