I'm trying to get combinations but I don't know how to do it

Question

In a test case, I have 1 2 3 4 as the inputs, I want to get

{1+2, 3+4}

{1+3, 2+4}

{1+4, 2+3}

but I only can do {1+2, 3+4} I can't think of any ways to get {1+3, 2+4}. I need some algorithm advice, can't think of any conditions to do this.

for (int j=0; j<woodLength.length; j++) {
        if (woodLength[j][2] != 1) {
            // a function that can create the boards using the wood pieces
            for (int i=0; i<woodLength.length; i++) {
                // set used boards as 1 and unused as 0
                if (woodLength[i][1] != 1) {
                    woodenBoardHeight.add(woodLength[i][0]+woodLength[i+1][0]);
                    System.out.println(woodenBoardHeight.get(wBHCount));
                    wBHCount ++;
                    woodLength[i][1] = 1;
                    woodLength[i+1][1] = 1;
                }
            }
            for (int i=0; i<woodLength.length; i++) {
                woodLength[i][1] = 0;
            }
            woodLength[j][2] = 1;
            woodLength[j+1][2] = 1;
        }
    }

this is my code, right now this prints {3,7} but I also want {4,6} and {5,5}

If it's helpful, I'm trying to solve CCC 2017 Senior S3 question

https://www.cemc.uwaterloo.ca/contests/computing/2017/stage%201/seniorEF.pdf

The problem is not really clear, do you always get _exactly four_ numbers as an input? If not, what do you want to calculate then? — Alex R, Aug 20 '20 at 15:24
If a builder has different lengths of boards (the inputs are the lengths and then the number of inputs are the number of boards, as an example {1 2 3 4} has 4 boards with a value of 1,2,3 and 4m respectively), the builder needs 2 boards to make a meter of a garden fence, and he wants to find all possible combinations of combining 2 boards together without duplicates, for example, boards with lengths 1, 2, 3, 4 can make a 3m fence and 7m fence or it can make a 4m and 6m or it can make a 5m and 5m fence, my program can only make the 3m and 7m fence — Ruijie Lu, Aug 20 '20 at 15:49
I don't see why you need to calculate the combinations for the problem you linked. It doesn't require you to output them. Instead you may only need to compute the sum of all pairs and save how often each sum appears. — Alex R, Aug 20 '20 at 16:41
Not even the sums of all pairs of pieces, just the number of appearances of each sum of distinct pairs of *lengths* (not overlooking the special case of pairing pieces with the same length). This is best viewed as a counting problem, not a combinatorial one. — John Bollinger, Aug 20 '20 at 16:45

Gilbert Le Blanc · Answer 1 · 2020-08-20T16:48:41.233

3

One algorithm to create all the combinations of an array makes use of an unsigned binary counter.

Array:  1  2  3  4

        0  0  0  0     [] empty combination
        0  0  0  1     [4]
        0  0  1  0     [3]
        0  0  1  1     [3, 4]

and so on.

In your case, you want the combinations that are 2 digits plus 2 digits. We can achieve this by testing the binary counter and creating the combination when the binary counter has exactly 2 bits on.

Array:  1  2  3  4

        0  0  1  1     [3, 4] & [1, 2]
        0  1  0  1     [2, 4] & [1, 3]
        0  1  1  0     [2, 3] & [1, 4]
        1  0  0  1     [1, 4] & [2, 3]
        1  0  1  0     [1, 3] & [2, 4]
        1  1  0  0     [1, 2] & [3, 4]

In your example, the order of the pairs is not important. You can eliminate the duplicate pairs, and you have the three conditions you're looking for.

edited Aug 20 '20 at 16:48

answered Aug 20 '20 at 16:37

Gilbert Le Blanc

50,182
6
67
111

how do I determine that the combination 0 0 1 1, for example, has been used? I thought of recording which ones have been used but it became really complicated so I wonder if there is a simpler way – Ruijie Lu Aug 21 '20 at 15:32
@Ruijie Lu: It's an unsigned binary counter. It counts up. 0, 1, 2, 3, etc. Once you've used 0011 (3), the counter (combination) will not return. – Gilbert Le Blanc Aug 21 '20 at 16:42
is this what you meant? https://www.geeksforgeeks.org/count-set-bits-in-an-integer/ nothing showed up when I typed in unsigned binary counter in google – Ruijie Lu Aug 22 '20 at 14:18
@Ruijie Lu: Yes. It's an int counter where you test (count) the bits. – Gilbert Le Blanc Aug 22 '20 at 15:10
After trying this I realized this doesn't work when I have 6 boards to work with, is there an alternative solution? If I wasn't clear enough, the input needs the number of boards and then the height of each board, the number of boards should be 2 <= N <= 100 000 – Ruijie Lu Aug 23 '20 at 15:45
@Ruijie Lu: After reading the problem statement, and thinking about it for a couple of hours, I have no idea what algorithm to use to pair the planks into boards. – Gilbert Le Blanc Aug 23 '20 at 17:43

score -1 · Answer 2 · answered Aug 21 '20 at 06:40

Use this code to get the solution as expected

 public static void main(String[] args) {
    List<Integer> num;
    Integer[] numArray = {1,2,3,4};
    num = Arrays.asList (numArray);
    List<Integer> newList = new ArrayList<> ();

    for(int i=1;i<num.size ();i++) {
        int[] intArray = new int[2];
        newList.addAll (num);
        newList.remove (0);
        newList.remove (i-1);
        intArray[0]=num.get (0)+num.get (i);
        intArray[1] = newList.get (0)+newList.get (1);
        System.out.println ("{"+intArray[0]+","+intArray[1]+"}");

    }
}

The Result will be like this :

{3,7}
{4,6}
{5,5}

I'm trying to get combinations but I don't know how to do it

2 Answers2