Code Golf: Permutations

Question

input: array of unique integers, sorted

output: all permutations. edit: output order is not important, as long as it's correct :-)

example:

[2, 6, 9]

output:

[ [2, 6, 9], [2, 9, 6], [6, 2, 9], [6, 9, 2], [9, 2, 6], [9, 6, 2] ]

Answer 1

Using Permutations in .NET for Improved Systems Security

Answer 2

A few easy ones, in alphabetical order...

Haskell

import Data.List
permutations

J

(A.~[:i.*/@:>:@i.@#)

Python

from itertools import permutations

Answer 3

C++

#include <algorithm>
std::next_permutation

Answer 4

Haskell without libraries (63 chars):

p(l)=case(l)of{_:_:_->l>>=(\i->map(i:)(p$filter(i/=)l));_->[l]}

Answer 5

Python without using libraries:

f=lambda a:a and[[e]+x for i,e in enumerate(a)for x in f(a[:i]+a[i+1:])]or[a]

Usage:

print f([2,6,9])

Answer 6

Haskell without libraries (42 chars)

p []=[[]]
p l=[a:b|a<-l,b<-p$filter(/=a)l]

Answer 7

Prolog

perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).

delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).

Answer 8

#include <string>
#include <vector>
#include <iostream>
using namespace std;
void Permute(string permutation,string dict){
    if(dict.length()==0)
     cout<<permutation;
    for(int i=0;i<dict.size();i++){
     Permute(permutation+dict[i],
      dict.substr(0,i)+dict.substr(i+1));
    }
}

Answer 9

Perl

Maybe not the most efficient nor shortest-code version, but I thought I'd give it a try for practice. Of course $ignore may be substituted by $i for shorter code.

p([2,6,9], []);

sub p {
  my ($a, $ignore) = @_;
  for(my $n = 0; $n <= $#$a; ++$n){
    if(!{map {$_ => 1} @$ignore}->{$n}){
      if($#$a == $#$ignore + 1){
        print join(",", map {$a->[$_]} (@$ignore, $n)), "\n";
      }
      else {
        p($a, [@$ignore, $n]);
      }
    }
  }
}

Answer 10

Implement permutations in Haskell (76 75 characters)

i e[]=[[e]]
i e(a:b)=(e:a:b):[a:s|s<-i e b]
f=foldr(\e->concatMap(i e))[[]]

Unlike some other Haskell answers, this one doesn't evaluate the elements of its input list.

I've been looking around for some prelude function that makes defining i (for "insert") more concise than the above, but so far I haven't found anything...

Answer 11

F#

I am using this as a way to learn F# so I would greatly appreciate anyone's suggestions on improving the code here, especially on the factorial calculation. Also, I try to avoid recursive functions whenever possible unless they can be made tail recursive, just as a personal challenge.

#light
let permutations lst =
    let result = ref [lst]
    for i = 1 to (List.fold (fun number product -> number * product) 1 [List.length(lst) .. -1 .. 1]) / (lst.Length - 1) do
        for start = 0 to (List.length(lst) - 2) do
            result := [List.permute (fun n -> match n with |_ when n=start->(start+1) |_ when n-1=start->start |_->n) (result.Value.Item(result.Value.Length-1))]
                      |> List.append result.Value
            ()
    Seq.take (result.Value.Length-1) result.Value // Have to get rid of the last one which is a duplicate of the given list.

permutations [2;6;9] |> Seq.iter (fun l -> printfn "%A" l)
System.Console.ReadKey(true) |> ignore

Answer 12

C# (not using recursion)

Not the shortest, but here's an implemenetation of Edsger Dijkstra's algorithm from the classic text A Discipline of Programming (Prentice-Hall). (I mostly just wanted to see if it could be done without recursion and have a play with generics).

static List<T> GetNext<T>(List<T> input) where T : IComparable<T>, IEquatable<T>    
{
    int N = input.Count;  
    int i, j; 
    for (i = N - 2; i > -1; i--)
        if (input[i].CompareTo(input[i+1]) < 0)                         
            break;          

    if (i < 0)
        return null;  

    j = N - 1;
    while (input[j].CompareTo(input[i]) <= 0)
        j = j - 1;     
    swap(input, i, j);   

    i+=2; j = N; 
    while (i < j)
    {
        swap(input, i - 1, j - 1);  
        i++;
        j--;
    }    
    return input;
}