开发者

combination of combination java

I need to find combination of combination in JAVA.

I have for instance 6 students in class. Out of them, I need to create combination of 4 people in group, and for each group I can choose an intimate group of 2.

I have to make sure that there are no doubles (order does not matter).! and need to print t开发者_如何学Pythonhe 4 people group.

However, this is the hard part:

So defining students with numbers:

If I print out 1234 as one of the combinations, I can't print out1256 as well, since 12 appears both in 1234 and in 1256.

How can I write it in Java?

EDITED

output of ([1,2,3,4,5],3,2) will be:

  1. Combinations without repetition (n=5, r=3) {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}

  2. deleting repeating groups of 2 elements, will leave me only: {1,2,3} {1,4,5} (i deleted groups that have combinations of 12,13,23,45,14,15 since they already appear in the first two that I have found.


Ok, here's the simple emulation of the process you described. But I use binary numbers to present set, it makes manipulations easier. For example, number 19 is 10011 in binary form: it means students 0, 3 and 4 are selected (there're 1's in those positions).

A little helper first.

// return all subsets of 'set', having size 'subsetSize'
Set<Integer> allSubsets(int set, int subsetSize) {
    Set<Integer> result = new HashSet<Integer>();
    if (subsetSize == 0) {
        result.add(0);
        return result;
    }
    if (set == 0) {
        return result;
    }

    // check if 1st element is present
    if (set % 2 == 1) {
        // use 1st element, one less element to collect
        for (Integer i : allSubsets(set / 2, subsetSize - 1)) {
            result.add(i * 2 + 1);
        }
    }
    // not use 1st element
    for (Integer i : allSubsets(set / 2, subsetSize)) {
        result.add(i * 2);
    }

    return result;
}

And main program. Suggestions are welcome.

    int N = 5;
    int M = 3;
    int Z = 2;

    List<Integer> result = new ArrayList<Integer>();

    // get all groups of M elements from 'wholeSet'
    int wholeSet = (1 << N) - 1;
    for (int s : allSubsets(wholeSet, M)) {
        // Check all subsets of 'Z' elements from set 's'
        boolean valid = true;
        for (int t : allSubsets(s, Z)) {
            // check if this Z-element subset already was used
            for (int past : result) {
                // check if 't' is subset of 'past' set
                if ((past|t) == past) {
                    valid = false;
                    break;
                }
            }
            if (!valid) {
                break;
            }
        }

        if (valid) {
            // none of Z-element subsets of 's' were used before
            result.add(s);
        }
    }

But it may require improvements (like memoization) for big inputs. But for now, since you don't say what kind of input you expect, I assume this is good enough.


Imagine you have a Student object with an equals comparing their Primarykey. In your example, student 1 will return 1, 2 will return 2 and so on.

Put them all in the set, this will ensure that there will be no double.

Iterate though the set by 4 then by 2 and will return you your desired result.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜