2
\$\begingroup\$

I want to know if my code is good, with reasonable efficiency, and if it is possible to improve my code and how. What would you suggest?

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class FindAllPermutationsWithRepetitions {

    public static void main(String[] args) {
        String str = "ferarri";
        Set<String> permutations = getPermutations(str);

        int i = 1;
        for(String s : permutations){
            System.out.println(i++ + ": " + s);
        }

        /* check correctness */
        System.out.println("\nThere must be " +  numOfArrangements(str) + " values");

    }

    public static Set<String> getPermutations(String remained){
        if(remained.length() <= 1){
            Set<String> set = new HashSet<String>();
            set.add(remained);
            return set;
        }

        char c = remained.charAt(0);
        Set<String> old_permutations = getPermutations(remained.substring(1));
        Set<String> new_permutations = new HashSet<String>();

        for(String old_s : old_permutations){
            for(int j = 0; j < old_s.length(); j++){
                new_permutations.add(old_s.substring(0, j) + c + old_s.substring(j));
            }
            new_permutations.add(old_s + c);
        }

        return new_permutations;
    }

    public static int factorial(int num){
        int result = 1;

        for (int i = 1; i <= num; i++) {
            result = result * i;
        }

        return result;
    }

    public static int numOfArrangements(String str){
        HashMap<Character, Integer> hm = new HashMap();

        for(char key : str.toCharArray()){
            if(hm.containsKey(key)) hm.put(key, hm.get(key) + 1);
            else hm.put(key, 1);
        }

        int divisor = 1;
        for(Integer value : hm.values()){
            divisor *= factorial(value);
        }

        return factorial(str.length()) / divisor;
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

My solution below uses a custom radix counter and then maps the value to each character in a given String. I have used BigInteger as you will hit problems with ints once your String gets to about 10 characters long, and the same problem with longs once your String gets to around 16 characters.

I have wrapped it all in one class so you can see it in action, but given the Counter class is completely independent, you should have that in it's own file.

package permutationgenerator;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Iterator;

public class StringPermutationGenerator implements Iterable<String> {
    private final String word;

    public StringPermutationGenerator(String word) {
        this.word = word;
    }

    @Override
    public Iterator<String> iterator() {
        return new StringIterator(word);
    }

    private class StringIterator implements Iterator<String> {
        private final char[] alphabet;
        private final Counter counter;
        private final BigInteger max;
        private BigInteger count;

        private StringIterator(String word) {
            alphabet = word.toCharArray();
            counter = new Counter(alphabet.length, alphabet.length);
            max = BigInteger.valueOf(alphabet.length).pow(alphabet.length);
            count = BigInteger.ZERO;
        }

        @Override
        public boolean hasNext() {
            return count.compareTo(max) < 0;
        }

        @Override
        public String next() {
            StringBuilder sb = new StringBuilder();
            for (int i : counter.getCounter()) {
                sb.append(alphabet[i]);
            }
            counter.increment();
            count = count.add(BigInteger.ONE);
            return sb.toString();
        }

    }

    private class Counter {
        private final int radix;
        private final int length;
        private final int[] counter;

        public Counter(int radix, int length) {
            this.radix = radix;
            this.length = length;
            counter = new int[length];
        }

        public int[] getCounter() {
            return counter;
        }

        public void increment() {
            for (int index = length - 1; ; index--) {
                if (index == -1) {
                    resetCounter();
                    return;
                }
                if (counter[index] < radix - 1) {
                    counter[index]++;
                    return;
                }
                counter[index] = 0;
            }
        }

        private void resetCounter() {
            Arrays.fill(counter, 0);
        }
    }
}

Usage is as such:

for (String s : new StringPermutationGenerator("ferrari")) {
    System.out.println(s);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.