LinkedHashSet and subList, getting n of collection

Question

I am trying to do a homework in math which is find a subset of collection {1,2,..,n} where n is a number given in the code, I cannot get it done with the sublist so I need to get your help with a math programming.

For example for n = 2:

[12]
[1][2]

It have 2 elements.

For example for n = 3:

[1][2][3]
[12][3]
[13][2]
[23][1]
[123]

It have 5 elements.

It have five elements.

For n = 4:

[1][2][3][4]
[12][3][4]
[13][2][4]
[14][2][3]
[23][1][4]
[24][1][3]
[34][1][2]
[12][34]
[13][24]
[14][23]
[123][4]
[124][3]
[134][2]
[234][1]
[1234]

It have 15 elements.

Do you have any ideas how to get it done?

I have tried many possibilites with LinkedHashSet and sublist inside loop but I had no clue for over 2h how to get it done, the output like this.

Is there any library in the Java to get this output? I would do that by manuall way, but there ahve to be different way.

import org.paukov.combinatorics.*;
import org.paukov.combinatorics.util.ComplexCombinationGenerator;

public class Main {
    public static void main(String args[]){

           // create a vector (A, B, B, C)
           ICombinatoricsVector<String> vector = Factory.createVector(new String[] { "1", "2", "3"});

           // Create a complex-combination generator
           Generator<ICombinatoricsVector<String>> gen = new ComplexCombinationGenerator<String>(vector, 1);
           Generator<ICombinatoricsVector<String>> gen2 = new ComplexCombinationGenerator<String>(vector, 2);
           Generator<ICombinatoricsVector<String>> gen3 = new ComplexCombinationGenerator<String>(vector, 3);
           // Iterate the combinations
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen2) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen3) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }

    }


}






([1, 2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 3], size=3)], size=1)
([1],[2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2, 3], size=2)], size=2)
([2, 3],[1]) - CombinatoricsVector=([CombinatoricsVector=([2, 3], size=2), CombinatoricsVector=([1], size=1)], size=2)
([2],[1, 3]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1, 3], size=2)], size=2)
([1, 3],[2]) - CombinatoricsVector=([CombinatoricsVector=([1, 3], size=2), CombinatoricsVector=([2], size=1)], size=2)
([1, 2],[3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2], size=2), CombinatoricsVector=([3], size=1)], size=2)
([3],[1, 2]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1, 2], size=2)], size=2)
([1],[2],[3]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2], size=1), CombinatoricsVector=([3], size=1)], size=3)
([1],[3],[2]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([3], size=1), CombinatoricsVector=([2], size=1)], size=3)
([3],[1],[2]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1], size=1), CombinatoricsVector=([2], size=1)], size=3)
([3],[2],[1]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([2], size=1), CombinatoricsVector=([1], size=1)], size=3)
([2],[3],[1]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([3], size=1), CombinatoricsVector=([1], size=1)], size=3)
([2],[1],[3]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1], size=1), CombinatoricsVector=([3], size=1)], size=3)

Well, these aren't normal subsets. A subset would contain elements 2,3,4 if the super set was 1,2,3,4,5. But you have different requirements. You seem to be dividing the super set into sets that contain all elements, but no elements in common with any subset. Or something like that. — markspace, Jun 22 '15 at 22:37
Yeah, I just need to get that output and I am trying to do that on sets, but I do not thinks it is possible at all, or my math thinking it is jsut too bad. — WinterTime, Jun 22 '15 at 22:47
You are right, I made mistake while creating that (from my mind). Also removed [23][14] [24][13] [34][12] — WinterTime, Jun 22 '15 at 22:52
The terminology for this is that you are looking for the ways to *partition* `{1,...,n}` into subsets. — Teepeemm, Jun 23 '15 at 00:32

Ely · Accepted Answer · 2015-06-23T00:04:11.413

This is combinatorics. See more information about the structure you need to understand, i.e. a permutation without repetition, also called a combination.

You might be interested in combinatoricslib, a Java library on Google Code, which you could use for your program.

You could also try to solve it without a library. That should not be too difficult. You'd need to use recursion I think.

I tested with List partitions:

import org.paukov.combinatorics.*;
import org.paukov.combinatorics.util.ComplexCombinationGenerator;

public class Main {

    public static void main(String args[]){

        // create a vector (1, 2, 3, 4)
        ICombinatoricsVector<String> vector = Factory.createVector(new String[] { "1", "2", "3", "4" });

        // Create a complex-combination generator
        Generator<ICombinatoricsVector<String>> gen = new ComplexCombinationGenerator<String>(vector, 2);

        // Iterate the combinations
        for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen) {
            System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
        }
    }
}

And the result was

([1],[2, 3, 4]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2, 3, 4], size=3)], size=2)
([2, 3, 4],[1]) - CombinatoricsVector=([CombinatoricsVector=([2, 3, 4], size=3), CombinatoricsVector=([1], size=1)], size=2)
([2],[1, 3, 4]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1, 3, 4], size=3)], size=2)
([1, 3, 4],[2]) - CombinatoricsVector=([CombinatoricsVector=([1, 3, 4], size=3), CombinatoricsVector=([2], size=1)], size=2)
([1, 2],[3, 4]) - CombinatoricsVector=([CombinatoricsVector=([1, 2], size=2), CombinatoricsVector=([3, 4], size=2)], size=2)
([3, 4],[1, 2]) - CombinatoricsVector=([CombinatoricsVector=([3, 4], size=2), CombinatoricsVector=([1, 2], size=2)], size=2)
([3],[1, 2, 4]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1, 2, 4], size=3)], size=2)
([1, 2, 4],[3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 4], size=3), CombinatoricsVector=([3], size=1)], size=2)
([1, 3],[2, 4]) - CombinatoricsVector=([CombinatoricsVector=([1, 3], size=2), CombinatoricsVector=([2, 4], size=2)], size=2)
([2, 4],[1, 3]) - CombinatoricsVector=([CombinatoricsVector=([2, 4], size=2), CombinatoricsVector=([1, 3], size=2)], size=2)
([2, 3],[1, 4]) - CombinatoricsVector=([CombinatoricsVector=([2, 3], size=2), CombinatoricsVector=([1, 4], size=2)], size=2)
([1, 4],[2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1, 4], size=2), CombinatoricsVector=([2, 3], size=2)], size=2)
([1, 2, 3],[4]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 3], size=3), CombinatoricsVector=([4], size=1)], size=2)
([4],[1, 2, 3]) - CombinatoricsVector=([CombinatoricsVector=([4], size=1), CombinatoricsVector=([1, 2, 3], size=3)], size=2)

I think that is what you were looking for. It needs some tweaking though (maybe ordering and adding the initial list elements like [1],[2],[3],[4]).

Already read that, but I have different requiremnts, all numbers in the collection have to be used. By using the combinatoricslib I will get for example of {1,2,3,4} : {}, {12}, {13} etc. — WinterTime, Jun 22 '15 at 22:59
Or simply use recursion to do it yourself. If I have time I'll try to come up with an example. — Ely, Jun 22 '15 at 23:03
I am trying to get it done with that library for now, I will come back with feedback. — WinterTime, Jun 22 '15 at 23:07
I have added a closest are but still didnt get the correct one. @edit — WinterTime, Jun 22 '15 at 23:24
Can you please first check if List partition could be of interest to you? With recursion I mean, that if you don't use the library, you would need to make recursive function calls. Not sure if you're acquainted with the concept of recursion. But check List partitions first please. I think that is what you're looking for. — Ely, Jun 22 '15 at 23:34
Yeah true that, but it shows multiply collections, so I will try to cut them off and thats what I needed, thanks! — WinterTime, Jun 22 '15 at 23:55
Hey ! I have found a way what I wanted, that output you given occur multipes of the collections, but I cut it off :) ([2],[1, 3, 4]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1, 3, 4], size=3)], size=2) ([1, 3, 4],[2]) - CombinatoricsVector=([CombinatoricsVector=([1, 3, 4], size=3), CombinatoricsVector=([2], size=1)], size=2) — WinterTime, Jun 23 '15 at 00:15

score 0 · Answer 2 · edited May 23 '17 at 12:29

0

This problem can be solved using dynamic programming wherein you break a complex problem into subsets.

I think this post might be useful: Combaintions of set of numbers

edited May 23 '17 at 12:29

Community

1
1

answered Jun 22 '15 at 22:55

alwaysAStudent

2,110
4
24
47

LinkedHashSet and subList, getting n of collection

2 Answers2