Skip to content

Instantly share code, notes, and snippets.

@jaycobbcruz
Last active February 16, 2022 09:20
Show Gist options
  • Star 15 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save jaycobbcruz/cbabc1eb49f51bfe2ed1db10a06a2b26 to your computer and use it in GitHub Desktop.
Save jaycobbcruz/cbabc1eb49f51bfe2ed1db10a06a2b26 to your computer and use it in GitHub Desktop.
Find all permutations of given items using Java 8
public class Permutations {
public static <T> Stream<Stream<T>> of(final List<T> items) {
return IntStream.range(0, factorial(items.size())).mapToObj(i -> permutation(i, items).stream());
}
private static int factorial(final int num) {
return IntStream.rangeClosed(2, num).reduce(1, (x, y) -> x * y);
}
private static <T> List<T> permutation(final int count, final LinkedList<T> input, final List<T> output) {
if (input.isEmpty()) { return output; }
final int factorial = factorial(input.size() - 1);
output.add(input.remove(count / factorial));
return permutation(count % factorial, input, output);
}
private static <T> List<T> permutation(final int count, final List<T> items) {
return permutation(count, new LinkedList<>(items), new ArrayList<>());
}
}
@jaycobbcruz
Copy link
Author

jaycobbcruz commented Apr 30, 2017

Permutations.of(Arrays.asList(1, 2, 3)).forEach(p -> { p.forEach(System.out::print); System.out.print(" "); });

will return:
123 132 213 231 312 321

@aronlausch
Copy link

Hey, can you please tell me which packages I have to include? It does´nt run on my Java.

@rokkbert
Copy link

import java.util.stream.*;

@SimonGreenaway
Copy link

Great code, note that if you have 13 or more items the code will silently break - use replace 'int' with 'long':

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.LongStream;
import java.util.stream.Stream;

/**
*

  • @author simon
    */
    public class Permutations2
    {
    public static Stream<Stream> of(final List items)
    {
    return LongStream.range(0, factorial(items.size())).mapToObj(i -> permutation(i, items).stream());
    }

    private static long factorial(final int num)
    {
    return LongStream.rangeClosed(2, num).reduce(1L, (x, y) -> x * y);
    }

    private static List permutation(final long count, final LinkedList input, final List output)
    {
    if (input.isEmpty()) { return output; }

     final long factorial = factorial(input.size() - 1);
     output.add(input.remove((int)(count / factorial)));
     return permutation(count % factorial, input, output);
    

    }

    private static List permutation(final long count, final List items)
    {
    return permutation(count, new LinkedList<>(items), new ArrayList<>());
    }
    }

@Azedyn
Copy link

Azedyn commented Jun 29, 2021

How to generate all permutations of 2 lists?

Permutations.of(list1, list2)

Thank you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment