how to print lexicographic permutations of 0,1,2 in java

Question

How to print lexicographic permutations of giving integer values. Example if i give 012 then output should be 012 021 102 120 201 210.

What i tried for achieve this,

package TEstingHere;

public class LexicographicPermutations {

    private static int permutationsFound = 0;

       public static void main(String[] args) {
          permuteTo("012", "");
       }

       private static void permuteTo(String s, String chosen) {
          if (s.length() == 0) {
             permutationsFound++;
             if (permutationsFound == 1000000) {
                System.out.println(chosen);
             }
          } else if (permutationsFound <= 1000000) {
             for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                String rest = s.substring(0, i) + s.substring(i + 1);
               // System.out.println(rest);
                permuteTo(rest, chosen + ch);
             }
             System.out.println(chosen);
          }
       }


}

but this code not satisfied my requirements.

someone tell me how to do this ?

Answer 1

I would implement the following algorithm, if we just need to print lexicographic permutations of a number: source wiki.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l greater than k such that a[k] < a[l].
Swap the value of a[k] with that of a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

Answer 2

Here is one way to approach it:

import java.util.List;
import java.util.ArrayList;

public class Main {


    public class LexicographicPermutations {

        private final String baseString;
        private final List<String> permutations = new ArrayList<String>();

        public LexicographicPermutations(String baseString) {
            this.baseString = baseString;
        }

        public List<String> getPermutations() {
            recursePermutations(baseString.length(), "");
            return permutations;
        }

        private void recursePermutations(int recursionsLeft, String result) {
            if(recursionsLeft == 0) {
                if(permutations.contains(result)) {
                    return;
                }
                int total = 0;
                StringBuilder resultTemp = new StringBuilder(result);
                for(int current = 0; current < baseString.length(); current ++) {
                    int position = resultTemp.indexOf(String.valueOf(baseString.charAt(current)));
                    if(position >= 0) {
                        resultTemp.deleteCharAt(position);
                    }
                }
                if (resultTemp.length() == 0) {
                    permutations.add(result);
                }
                return;
            }
            for(int index = 0; index < baseString.length(); index ++) {
                recursePermutations(recursionsLeft - 1, result + baseString.charAt(index));
            }
        }
    }

    public static void main(String[] args) {
        for(String permutation : new Main().new LexicographicPermutations("012").getPermutations()) {
            System.out.println(permutation);
        }
    }
}

Answer 3

My version disassembles the string into a charArray, sorts the array, counts the characters occurences and writes them into a Map and then builds a recursive tree with a for loop that avoids duplicates from the start. So my version runs in O(c^n) even if one character occurs multiple times and is guranteed to be correct. Moishe Lipskers version should be a bit slower when a characters occurs more than once and I think that nogards solution might produce duplicates, but I'm not sure on that.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LexicographicPermutations {

    public static void main(String[] args) {
        System.out.println(permute("3211"));
    }

    private static String permute(String inputString) {
        //for permutations we must disregard equal
        final Map<String, Integer> inputAlphabet = new HashMap<String, Integer>();
        final Map<String, Integer> disregard = new HashMap<String, Integer>();
        final StringBuilder output = new StringBuilder();
        final char[] inputAsCharArray = inputString.toCharArray();
        Arrays.sort(inputAsCharArray);
        for(final char c : inputAsCharArray) {
            if(inputAlphabet.containsKey(""+c)) {
                inputAlphabet.put(""+c, inputAlphabet.get(""+c)+1);
            }else {
                inputAlphabet.put(""+c, 1);
            }
        }
        permute(inputAlphabet,disregard," ", inputString.length(), output);
        return output.toString();
    }

    private static String permute(Map<String, Integer> inputAlphabet, Map<String, Integer> disregard, String start, int length, StringBuilder output) {
        final StringBuilder sb = new StringBuilder();
        for(final String s : inputAlphabet.keySet()) {
            for(int i = 0; i < (inputAlphabet.get(s)-(disregard.containsKey(s)?disregard.get(s):0)); i++) {
                if(disregard.containsKey(s)) {
                    disregard.put(s, disregard.get(s)+i+1);
                }else {
                    disregard.put(s, i+1);
                }
                sb.append(permute(inputAlphabet,disregard, start+s, length-1,output));
                if((disregard.get(s)-i-1) != 0) {
                    disregard.put(s, disregard.get(s)-i-1);
                }else {
                    disregard.remove(s);
                }
            }
        }
        if(sb.length() == length) {
            output.append(start+sb.toString());
            return start+sb.toString();
        }else {
            return start+sb.toString();
        }
    }
}