How to create all combinations for items in an Array?-CodePudding

I did see this and this post on it, but it is not in Java or Kotlin, so it doesn't help me. Now, coming to the problem, I want to be able to create all the possible combinations for an array. For example, I have this array:

[1,2,3,4]

And then all the possible combinations give us this:

[1,2,3,4]
[1,2,4,3]
[1,3,2,4]
[1,3,4,2]
[1,4,2,3]
[1,4,3,2]

[2,1,4,3]
[2,1,3,4]
[2,3,1,4]
[2,3,4,1]
[2,4,3,1]
[2,4,1,3]

[3,1,2,4]
[3,1,4,2]
[3,2,4,1]
[3,2,1,4]
[3,4,1,2]
[3,4,2,1]

[4,1,2,3]
[4,1,3,2]
[4,2,3,1]
[4,2,1,3]
[4,3,2,1]
[4,3,1,2]

I don't want to have a space between these two different starts or numbers. I just added it for readability.

It should not only work for Integers but also for objects like strings, our classes, etc...

So, how can I achieve this in Java or Kotlin?

I also just came across this post, but it wanted for two arrays and needed for one. Also, it was closed, so I felt it better to ask another one.

Pls, don't downvote. Just let me know what can be better.

CodePudding user response：

If the task is not to implement the algorithm which generates the permutations you need, I would recomend to use a library like combinatoricslib3. If you happen to use Guava or Apache Commons in your projects, those have also some methods to generate combinations / permutations from a given collection. With combinatoricslib3 your code could look something like:

import org.paukov.combinatorics3.Generator;

public class Example {

    public static void main(String[] args) {
        Integer[] array = {1,2,3,4};
        Generator.permutation(array)
                .simple()
                .stream()
                .forEach(System.out::println);

        //Example with strings

        Generator.permutation("apple", "orange", "cherry")
                .simple()
                .stream()
                .forEach(System.out::println);
    }
}

output:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
....

and

[apple, orange, cherry]
[apple, cherry, orange]
[cherry, apple, orange]
[cherry, orange, apple]
[orange, cherry, apple]
[orange, apple, cherry]

CodePudding user response：

It seems that you expect to generate all possible permutations (N!), not combinations of given set of objects. Please check Guava's library Collections2.permutations.

It takes collection of elements, and return Collection of Lists of those elements.

public class Permutations {

public static void main(String[] args) {
    List<Integer> myList = List.of(1,2,3,4);
    // generate permutations of myList
    var permutations = Collections2.permutations(myList);
}

}

CodePudding user response：

Without using a library:

fun List<Any>.permutations(): List<List<Any>> {
  if (isEmpty()) return listOf(emptyList())
  return indices.fold(mutableListOf()) { result, i ->
    (result   (this - this[i])
      .permutations()
      .fold(mutableListOf()) { acc, item ->
        acc.add(item   this[i])
        acc
      }
    ).toMutableList()
  }
}

listOf(1, 2, 3, 4).permutations().forEach(::println)

listOf("A", "B", "C", "D").permutations().forEach(::println)

data class Test (val name: String)
listOf(Test("A"), Test("B"), Test("C"), Test("D")).permutations().forEach(::println)