Subj : Re: Algorithm to generate permutation for a non sequential single array
To   : comp.programming
From : Jon Harrop
Date : Tue Jul 05 2005 07:24 pm

mmarin1m@hotmail.com wrote:
> I'm looking for an algorithm that would generate all permutations for a
> given non sequential list.

As others have already said, you are asking for the list of all subsets,
nothing to do with permutations.

The following 3-line OCaml function does this:

  let rec subsets = function
      [] -> [[]]
    | h :: t -> (fun t -> List.map (fun t -> h :: t) t @ t) (subsets t);;

For example:

# let rec subsets = function
    [] -> [[]]
  | h :: t -> (fun t -> List.map (fun t -> h :: t) t @ t) (subsets t);;
val subsets : 'a list -> 'a list list = <fun>
# subsets [125; 126; 5; 88; 33];;
- : int list list =
[[125; 126; 5; 88; 33]; [125; 126; 5; 88]; [125; 126; 5; 33]; [125; 126; 5];
 [125; 126; 88; 33]; [125; 126; 88]; [125; 126; 33]; [125; 126];
 [125; 5; 88; 33]; [125; 5; 88]; [125; 5; 33]; [125; 5]; [125; 88; 33];
 [125; 88]; [125; 33]; [125]; [126; 5; 88; 33]; [126; 5; 88]; [126; 5; 33];
 [126; 5]; [126; 88; 33]; [126; 88]; [126; 33]; [126]; [5; 88; 33]; [5; 88];
 [5; 33]; [5]; [88; 33]; [88]; [33]; []]

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.