CODEWITHSUNDEEP
javaalgorithmpermutation
Liondancer
Liondancer

Reputation: 16469

permutation of any length with duplicates

I am trying to find the permutations of any length of a given string. This includes duplicates

For example:

str = "java";

At length 1

j, a, v, a

At length 3

4!/(4-3)! = 24 

jav, jaa, jva, jva, jaa, jav,
ajv, aja, avj, ava, aaj, aav,
vja, vja, vaj, vaa, vaj, vaa,
aja, ajv, aaj, aav, avj, ava

I was thinking about using a for loop to iterate through each character of the string and perform he computation necessary to produce the permutations for the rest of the string

ex: 

start with "j"
    av, aa | va, va | aa, av

then with the first "a"
    jv, ja | vj, va | aj, av

This is what I have so far and I am still in the process of figuring out the logic behind solving this problem:

public static class Pair<Character, Boolean> {
    Character letter;
    Boolean used;
    Pair(Character c, Boolean seen) {
        this.used = seen;
        this.letter = c;
    }
}

public static void permutationOfString(String str, int len) {
    List<Pair> charCheck = new ArrayList<Pair>();
    for (int i = 0; i < str.length(); i++) {
        charCheck.add(new Pair(str.charAt(i), false));
    }

    for (char c : str.toCharArray()) {

    }
}

I am unsure how to perform write this. I would like to output all the possible permutations of the string.

If anyone has another way of solving this or can do this much more efficiently I am open to suggestions! Thanks!

Upvotes: 1

Views: 598

Answers (3)

Jakub Jirutka
Jakub Jirutka

Reputation: 10817

You can use Apache Commons Collections and Apache Commons Lang:

String str = "java";
List<Character> strChars = Arrays.asList(ArrayUtils.toObject(str.toCharArray()));

Collection<List<Character>> charPermutations = CollectionUtils.permutations(strChars);

List<String> result = new ArrayList<>();
for (List<Character> chars : charPermutations) {
    result.add(StringUtils.join(chars, ""));
}

…or Guava Libraries:

String str = "java";
List<Character> strChars = Chars.asList(str.toCharArray());

Collection<List<Character>> charPermutations = Collections2.permutations(strChars);

Collection<String> result = Collections2.transform(charPermutations, new Function<List<Character>, String>() {
    public String apply(List<Character> input) {
        return new String(Chars.toArray(input));
    }
});

However, if you’re using Java 8, it can be done a little bit gracefully then this insanity (but still cannot be compared with elegance of Groovy…).

Upvotes: 1

user3276611
user3276611

Reputation: 1

Here's a method for returning the factorial of an int so you can just put the length of the string in like this 

factorial("java".length);


public static int factorial(int n) {
    int fact = 1; // this  will be the result
    for (int i = 1; i <= n; i++) {
        fact *= i;
    }
    return fact;
}

but it seems like you're trying to find the number of possible combinations based on the amount of letters in a certain word like in your example with java they're are 3 distinct letters. So it seems you want to know how many permutations of that word at length 3 there are in which case would be the length with an exponoent of how many possible combinations there are.

Upvotes: 0

peter.petrov
peter.petrov

Reputation: 39457

Append something to each one of them to make them unique.
Run the regular algorithm for non-duplicates.
Strip the appended texts before outputting the results.

Upvotes: 1

Related Questions