Java Permutations of String given an Integer Number

Question

I am trying to do permutations in java of a String given an Integer Number.

So if the String is "abc" and the Integer Number is 2.

I want the following results:

ab ac ba bc ca cb

If the String is also "abc" but the Integer Number is 3, I want the following results:

abc bac cba bca cab acb

I have already the following method:

private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) permutationsList.add(prefix);
        else {
            for (int i = 0; i < n; i++)
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
        }
    }

But this only works for the Integer Number equals to the String size, in this case 3.

So can something help me to make this work, with a Integer argument?

Thanks alot in advance ;)

I suppose this might help: http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string — Michał Szydłowski, Jun 02 '14 at 13:47

score 1 · Accepted Answer · answered Jun 02 '14 at 14:08

One of the best way to do permutation of a data set is to by applying DFS , it help making all combination of a specified length .

Here is my solution for your problem :

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

/**
 * @author mifmif
 * 
 */
public class DFS {

    /**
     * list of generated combination
     */
    List<String> permutations = new ArrayList<String>();
    /**
     * input used to generate combination
     */
    String input = "ABCDEF";
    /**
     * the length of the combination
     */
    int conbinationSize = 3;
    /**
     * isChoosed[i] is true if the combination that is currently prepared
     * contain index.charAt(i)
     */
    boolean[] isChoosed = new boolean[input.length()];

    /**
     * the DFS method that will generate all possible combination
     * 
     * @param partialOutput
     */
    public void generateCombination(String partialOutput) {
        if (partialOutput.length() == conbinationSize) {
            permutations.add(partialOutput);
            return;
        }
        for (int i = 0; i < input.length(); ++i) {
            if (!isChoosed[i]) {
                isChoosed[i] = true;
                generateCombination(partialOutput + input.charAt(i));
                isChoosed[i] = false;
            }
        }

    }

    void printCombination() {
        for (String c : permutations) {
            System.out.println(c);
        }
    }

    public static void main(String[] args) {
        DFS dfs = new DFS();
        dfs.generateCombination("");
        dfs.printCombination();
    }
}

timgeb · Answer 2 · 2014-06-02T14:03:04.447

0

Take a step back from your IDE/editor and think about how to solve this problem in pseudocode, at a higher level.

What should happen if the length of the string is zero or the integer k is zero? How do you get the permutations if k is equal to the length of the string? If your string is 'ABC' you would get all the permutations starting with 'A' by finding all the permutations of 'BC' and appending each of them to the letter 'A'. So what happens now in order to to get the permutations of 'ABC' starting with 'B' and 'C'?

Finally, ask yourself at what step you would need to stop the process if k is smaller than the length of the string.

Some pseudo-code:

perms(string, k)
    if length(string) == 0 or k == 0
         // do what?
    else
       for every character in string
           for every sub-permutation in perms(*some modified string*, *some modified k-value*)
                // the permutation is character + sub-permutation

edited Jun 02 '14 at 14:03

answered Jun 02 '14 at 13:49

timgeb

76,762
20
123
145

Thanks for your help, but I am so slow today . I can not think well . I know that if length(string) == 0 or k == 0 I need to return empty String right? But for the other case I don't know :s – TiagoM Jun 02 '14 at 14:09
Yes, a zero-length string or a k value of zero is your simple case for which the permutation would be the empty string. Another hint: the sub-permutation should reduce in size each recursive call. If that's not clear try to understand the version of the function which does not take a k parameter first. What should happen to k now? Would it not be great if k reached zero before the length of the *some modified string* reached zero? – timgeb Jun 02 '14 at 14:13

Java Permutations of String given an Integer Number

2 Answers2