Make all possible combinations of URL with the String

Question

I am trying to make a url from a different combinations of string separated by comma so that I can use those url to execute them and get the data back.

I have simplified something like this, I have a HashSet that will contain all my strings, not A,B,C in real. I just modified it here to make it simple.

Set<String> data = new HashSet<String>();
h.add("A");
h.add("B");
h.add("C");    

for (int i = 1; i < 1000; i++) {

String pattern = generateString(data);

String url = "http://localhost:8080/service/USERID=101556000/"+pattern;

System.out.println(url);

}

/**
 * Below is the method to generate Strings.
 /
private String generateString(HashSet<String> data) {

//not sure what logic I am supposed to use here?

}

So the output should be something like this-

http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/C,A

--
And other combinations

The above output can be in any random order as well. But it should be all the possible combinations. And if all the possible combinations are finished then start again.

Any suggestion how can I achieve the above problem definition?

From what I can tell, a URL has nothing to do with your problem. You've got a Collection as input and you want to permute all possibilities. There are many articles on how to do that on stackoverflow. — Daniel Kaplan, Feb 15 '13 at 01:30
Do you want permutations or combinations? Either way, feel free to use Google or the SO search facility. This topic has been discussed here previously. — Code-Apprentice, Feb 15 '13 at 01:45
Any particular combinations of String with commas in between. So that I can plugin those into the URL — AKIWEB, Feb 15 '13 at 01:45
Then you should probably name your method `generateCombinations()` in order to avoid confusion... — Code-Apprentice, Feb 15 '13 at 01:46
Searching for [java combination generator](https://www.google.com/search?setmkt=en-US&q=java+combination+generator) brings up useful results. You need to generate all combinations for all sizes 1 through `data.size()` — Miserable Variable, Feb 15 '13 at 01:51
And the method needs to either return a set or a [generator](http://en.wikipedia.org/wiki/Generator_(computer_programming)) — Miserable Variable, Feb 15 '13 at 01:53

score 3 · Answer 1 · answered Feb 15 '13 at 01:39

3

What you're asking is not trivial.

Let's look at 2 strings, A and B.

Here are all of the permutations.

A
B
AB
BA

Ok, let's look at 3 strings, A, B, and C.

Here are all the permutations.

A
B
C
AB
AC
BA
BC
CA
CB
ABC
ACB
BAC
BCA
CAB
CBA

Do you see a pattern yet?

First, you have to find all of the single string permutations. Then the two string permutations. Then the three string permutations. And so on, up to the number of strings.

Then, within a set of permutations (like the two string set), you have to find all of the possible permutations.

You can do this with java loops. You can also use recursion.

answered Feb 15 '13 at 01:39

Gilbert Le Blanc

50,182
6
67
111

1

While the idea is similar, the OP is asking for *combinations* in the text (and supported by the example) despite the word "permutation" in the method name. – Code-Apprentice Feb 15 '13 at 01:44
1

I disagree. In his output example, CA is a permutation. – Gilbert Le Blanc Feb 15 '13 at 01:46
That depends on if you interpret it as a set or a list. Since AC isn't given as well, I take it as a set. – Code-Apprentice Feb 15 '13 at 02:36

score 2 · Accepted Answer · edited Jan 10 '14 at 19:51

Given what is k-arrangement (http://en.wikibooks.org/wiki/Probability/Combinatorics), you are looking for the k-arrangement where k varies from 1 to D, where D is the size of the data collections.

This means to compute - my first post I can't post image so look at equation located at :

In order to do it, you can make k varies, and the for each k may n varies (i.e. deal only with a sub array or data to enumerate the k-permutations). These k-permutations can be found by walking the array to the right and to the left using recursion.

Here is a quick bootstrap that proves to enumerate whart is required :

public class EnumUrl {

private Set<String> enumeration = null;
private List<String> data = null;
private final String baseUrl = "http://localhost:8080/service/USERID=101556000/";

public EnumUrl(List<String> d) {
    data = d;
    enumeration = new HashSet<String>(); // choose HashSet : handle duplicates in the enumeration process
}

public Set<String> getEnumeration() {
    return enumeration;
}

public static void main(String[] args) {

    List<String> data = new ArrayList<String>();
    data.add("A");
    data.add("B");
    data.add("C");

    EnumUrl enumerator = new EnumUrl(data);

    for (int k = 0; k < data.size(); k++) {

        // start from any letter in the set
        for (int i = 0; i < data.size(); i++) {
            // enumerate possible url combining what's on the right of indice i
            enumerator.enumeratePossibleUrlsToRight(data.get(i), i);

            // enumerate possible url combining what's on the left of indice i
            enumerator.enumeratePossibleUrlsToLeft(data.get(i), i);
        }

        // make a circular permutation of -1 before the new iteration over the newly combined data
        enumerator.circularPermutationOfData();
    }

    // display to syso
    displayUrlEnumeration(enumerator);
}

private void circularPermutationOfData() {
    String datum = data.get(0);
    for (int i = 1; i < data.size(); i++) {
        data.set(i - 1, data.get(i));
    }
    data.set(data.size() - 1, datum);
}

private static void displayUrlEnumeration(EnumUrl enumerator) {
    for (String url : enumerator.getEnumeration()) {
        System.out.println(url);
    }
}

private void enumeratePossibleUrlsToRight(String prefix, int startAt) {
    enumeration.add(baseUrl + prefix);
    if (startAt < data.size() - 1) {
        startAt++;
        for (int i = startAt; i < data.size(); i++) {
            int x = i;
            enumeratePossibleUrlsToRight(prefix + "," + data.get(x), x);
        }
    }
}

private void enumeratePossibleUrlsToLeft(String prefix, int startAt) {
    enumeration.add(baseUrl + prefix);
    if (startAt > 0) {
        startAt--;
        for (int i = startAt; i >= 0; i--) {
            int x = i;
            enumeratePossibleUrlsToLeft(prefix + "," + data.get(x), x);
        }
    }
}
}

The program outputs for {A,B,C} :

http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/B,A,C
http://localhost:8080/service/USERID=101556000/B,C,A
http://localhost:8080/service/USERID=101556000/B,A
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/C,B,A
http://localhost:8080/service/USERID=101556000/A,C,B
http://localhost:8080/service/USERID=101556000/A,C
http://localhost:8080/service/USERID=101556000/A,B
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/C,B
http://localhost:8080/service/USERID=101556000/C,A
http://localhost:8080/service/USERID=101556000/C,A,B

And for {A,B,C,D} :

http://localhost:8080/service/USERID=101556000/B,A,D,C
http://localhost:8080/service/USERID=101556000/C,D
http://localhost:8080/service/USERID=101556000/A,D,C,B
http://localhost:8080/service/USERID=101556000/A,C,D
http://localhost:8080/service/USERID=101556000/D
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/A,C,B
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/A,B,C,D
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/D,C,B,A
http://localhost:8080/service/USERID=101556000/C,B,A,D
http://localhost:8080/service/USERID=101556000/A,B,D
http://localhost:8080/service/USERID=101556000/D,B
http://localhost:8080/service/USERID=101556000/D,C
http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/D,C,A
http://localhost:8080/service/USERID=101556000/D,C,B
http://localhost:8080/service/USERID=101556000/C,D,A
http://localhost:8080/service/USERID=101556000/C,D,B
http://localhost:8080/service/USERID=101556000/D,A
http://localhost:8080/service/USERID=101556000/A,D,C
http://localhost:8080/service/USERID=101556000/A,D,B
http://localhost:8080/service/USERID=101556000/C,B,D
http://localhost:8080/service/USERID=101556000/B,A,D
http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/B,A,C
http://localhost:8080/service/USERID=101556000/B,C,A
http://localhost:8080/service/USERID=101556000/B,A
http://localhost:8080/service/USERID=101556000/B,C,D
http://localhost:8080/service/USERID=101556000/C,B,A
http://localhost:8080/service/USERID=101556000/A,D
http://localhost:8080/service/USERID=101556000/D,A,B
http://localhost:8080/service/USERID=101556000/A,C
http://localhost:8080/service/USERID=101556000/D,A,C
http://localhost:8080/service/USERID=101556000/B,C,D,A
http://localhost:8080/service/USERID=101556000/A,B
http://localhost:8080/service/USERID=101556000/B,D
http://localhost:8080/service/USERID=101556000/C,D,A,B
http://localhost:8080/service/USERID=101556000/D,A,B,C
http://localhost:8080/service/USERID=101556000/D,B,A
http://localhost:8080/service/USERID=101556000/D,B,C
http://localhost:8080/service/USERID=101556000/B,D,A
http://localhost:8080/service/USERID=101556000/C,B
http://localhost:8080/service/USERID=101556000/C,A,D
http://localhost:8080/service/USERID=101556000/C,A
http://localhost:8080/service/USERID=101556000/B,D,C
http://localhost:8080/service/USERID=101556000/C,A,B

Which is not the exhaustive enumeration. Basically we should have:

(my first post I can't post image to look at equation located in my reply, I don't have the reputation to post 2 links ... #omg)

That makes 64 combinaisons, distributed as follows:

4 combinaisons of 1 element (k=1)
12 combinaisons of 12 element (k=2)
24 combinaisons of 24 element (k=3)
24 combinaisons of 24 element (k=4)

You can see that my program is OK for k=1, k=2, and k=3. But there are not 24 combinaisons for k=4. In order to complete the program, you will need to iterate also on other type of shuffling the data than circular permutation. Actually when k=4, circular permutation does not generate for instance ADBC as input data (hence DBCA cannot be generated by my implementation for instance). In this case, you will want to enumerate all possible data input array with n elements in all possible order. This is a special case of k-permutation, where k=n, and therefore leads to finding the n! permutation. We can achieve this by calling the EnumUrl method for each of the n! possible permutation.

For this, you should update EnumUrl enumerator = new EnumUrl(data); accordingly, but I guess I am letting some work for you to make :-)

HTH

And the second equation I could not post becasue as a new user I don't have the "reputation" islocated at : http://i.stack.imgur.com/my6wv.gif — Fafhrd, Feb 15 '13 at 09:31

score 1 · Answer 3 · edited May 23 '17 at 12:12

A short version working for arbitrary set size, with generics, using guava, and the method for permutation given here.

Basically the idea is the following :

Generate the powerset, discard empty set

For each set of the powerset, generate all permutations

public class QuickEnumeration {

Set<T> objects;

public QuickEnumeration(Set<T> objects) {
    this.objects = objects;
}

public List<List<T>> generateEnumeration() {
    List<List<T>> result = new ArrayList<List<T>>();
    // Compute the powerset
    Set<Set<T>> powerset = Sets.powerSet(objects);
    for (Set<T> set : powerset) {
        // Discard empty set
        if (set.size() > 0) {
            // Arraylist faster for swapping
            ArrayList<T> start = new ArrayList<T>(set);
            permute(start, 0, result);
        }
    }
    return result;
}

private void permute(ArrayList<T> arr, int k, List<List<T>> result) {
    for (int i = k; i < arr.size(); i++) {
        java.util.Collections.swap(arr, i, k);
        permute(arr, k + 1, result);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        result.add((List<T>) arr.clone());
    }
}

public static void main(String[] args) {
    Set<String> testSet = new HashSet<>();
    testSet.add("A");
    testSet.add("B");
    testSet.add("C");
    QuickEnumeration<String> enumerate = new QuickEnumeration<>(testSet);
    System.out.println(enumerate.generateEnumeration());
}

}

Testing with "A","B","C" gives :

[[A], [B], [A, B], [B, A], [C], [A, C], [C, A], [B, C], [C, B], [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, B, A], [C, A, B]]

Prince · Answer 4 · 2013-02-15T02:31:55.750

I am not entirely sure what you really want, so I ended up writing this piece of code for you. Hope it gets you started!

public static void doThis() {

    String url1="http://www.example.com";
    String string1="A";
    String url2="http://www.foo.com";
    String string2="B";
    String url3="http://www.bar.com";
    String string3="C";

    Map<String, String> abbrMap = new HashMap<String, String>();
    abbrMap.put(string1, url1);
    abbrMap.put(string2, url2);
    abbrMap.put(string3, url3);
    String string = string1+string2+string3;
    for(Map.Entry<String, String> m : abbrMap.entrySet()) {
        arrange(string, m.getValue());
    }

}

private static void arrange(String str, String url) {
    if (str.length()==0) return;
    StringBuffer sbuf = new StringBuffer();
    for (int j=0; j<str.length(); j++) {

        for(int i=j; i<str.length(); i++) {
            char c = str.charAt(i);
            sbuf.append(c);
            System.out.println(url+"/"+sbuf.toString());
            sbuf.append(",");
        }
        sbuf.setLength(0);
    }
}

Output:

http://www.example.com/A
http://www.example.com/A,B
http://www.example.com/A,B,C
http://www.example.com/B
http://www.example.com/B,C
http://www.example.com/C
http://www.foo.com/A
http://www.foo.com/A,B
http://www.foo.com/A,B,C
http://www.foo.com/B
http://www.foo.com/B,C
http://www.foo.com/C
http://www.bar.com/A
http://www.bar.com/A,B
http://www.bar.com/A,B,C
http://www.bar.com/B
http://www.bar.com/B,C
http://www.bar.com/C

Like I said it's not clear from what is asked above. What he meant by `"Any other combinations"`? The combinatorial ideas will be clear if the question is made clear. Then, it's all about logic. — Prince, Feb 15 '13 at 03:18
Despite unclear question, I don't see a clear relationship between each String and the URL, so a Map is inappropriate. — Code-Apprentice, Feb 15 '13 at 03:24
Well, as you can see the main work is done by the `arrange()` method in my code. I have used a map just to capture urls and generate the desired output. The method can be modified and used accordingly. — Prince, Feb 15 '13 at 03:47
Despite unclear question, I have tried my best to answer it and with all that effort I think that -1 is harsh. — Prince, Feb 15 '13 at 15:00
Two `Lists` would be more appropriate than a `Map`. One list for the URLs and another list for the other Strings. IMO, it is very important to understand data structures and use the appropriate one for a given task. — Code-Apprentice, Feb 16 '13 at 01:03

Make all possible combinations of URL with the String

4 Answers4