All possible permutations of words in a sentence

Question

I have a sentence,

I love java coding

I need to write a function that returns an array list of all possible permutations of words in the sentence, viz

I java love coding
I coding love java
.........

I have split the sentence into an ArrayList and now at a loss as to how to go about the task efficiently. C++ has a function nextPermutaion() which provides a out of the box solution. Does java provide something similar. If not what would be an efficient way to get this done.

@cricket_007 the first part of my questions still doesn't get answered. Is there an out of the box solution provided by Java. — Zeus, Mar 23 '16 at 15:44
It implicitly answers it : if people ask questions and are answered with custom code, it probably means there is no out-of-the box solution. — Aaron, Mar 23 '16 at 15:45
A String is just a list of characters. The idea is the same. Take a sublist, recurse on it, add one element back in each time. — OneCricketeer, Mar 23 '16 at 15:47

score 1 · Answer 1 · edited May 23 '17 at 11:45

This problem is equivalent to the one of generating all possible permutations of a set of n numbers, where n is the number of words in a sentence.

Convert the sentence to an ArrayList<String> words of words and then generate permutations of an array {0,1,...,n-1} so that each permutation arr represents the permutation of words in the sentence: words[arr[0]], ..., words[arr[n-1]].

As for the problem of computing all permutations of an array, there are plenty of examples of that here on SO.

Below is an example of a code for generating all permutations of a list (taken from this answer by @YevgenYampolskiy). That code computes all permutations of a List<Integer> and can easily be adapted to compute permutations of a List<String> (ArrayList<String> implements List<String>).

public class Permute{
    static void permute(java.util.List<Integer> arr, int k){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            System.out.println(java.util.Arrays.toString(arr.toArray()));
        }
    }
    public static void main(String[] args){
        Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0);
    }
}

The question has already been marked as a duplicate. Don't copy answers from other places. — OneCricketeer, Mar 23 '16 at 15:55
I have only copied a small snippet of code (and referenced the rather long answer from which the snippet was taken as well as explicitly acknowledged the author of the snippet). The rest of the answer (the non-code part) is NOT copied. I don't appreciate the condescending tone of your comment. — blazs, Mar 23 '16 at 15:59

SkyLeach · Answer 2 · 2016-03-23T15:51:55.247

0

AFAIK the java core collections doesn't provide any permutations functions (like you might find in the Python Set classes).

Guava (google java libs) provide iterable permutations as a part of collections2 (documented here).

If you don't want to use a third-party library you are going to have to roll your own algorithm.

edited Mar 23 '16 at 15:51

answered Mar 23 '16 at 15:48

SkyLeach

1,363
13
15

@cricket_007 you are, of course, correct. Personal habit, I'm jaded against branding of core libraries I guess. – SkyLeach Mar 23 '16 at 15:53

All possible permutations of words in a sentence

2 Answers2