D
D
Dmitry Smerks2019-01-23 17:10:28
Java
Dmitry Smerks, 2019-01-23 17:10:28

How to implement a combinatorics algorithm in a program?

Hello, I recently stumbled upon such a task, I thought that it was very easy, but I was mistaken. Combinatorics problem. I am attaching the text to the application. The point, in short, is to pick up 9 numbers in the range from 1..20 without repeating. So that the sum of certain numbers of numbers is equal to the sum of others. That is, the cycle
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 8 11
1 2 3 4 5 6 7 8 12
And such checks go on and on until we find coincidence.
Tried to make a loop for the selection, but it repeats the value:

for (int a = 1; a < 21; a++) {
            for (int b = 1; b < 21; b++) {
                for (int c = 1; c < 21; c++) {
                    for (int d = 1; d < 21; d++) {
                        for (int e = 1; e < 21; e++) {
                            for (int f = 1; f < 21; f++) {
                                for (int g = 1; g < 21; g++) {
                                    for (int h = 1; h < 21; h++) {
                                        for (int y = 1; y < 21; y++) {
                                            circle[1].value = a;
                                            circle[2].value = b;
                                            circle[3].value = c;
                                            circle[4].value = d;
                                            circle[5].value = e;
                                            circle[6].value = f;
                                            circle[7].value = g;
                                            circle[8].value = h;
                                            circle[9].value = y;

The task was VERY hooky, but experience, unfortunately, is not enough. I hope you help me out5c4875cec9596366747703.jpeg

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2019-01-24
@wataru

First, convert the picture from zalachi to numbers. Here you have 20 points, numbered from 1 to 20, somehow. Write down all 12 groups (9 circles and 3 diameters). You will have 12 sets of 5-6 numbers. Write them in the program as constant arrays.
Then do iteration by recursion: In your global array or list in the parameter there will be a set of numbers that have not yet been set. First check that you have not already made 2 groups with different amounts. Go through all 9 + 3 groups, if one is already completely filled, then write its sum into a variable for the circle or diameter, respectively. If before recording there was already another amount, then you found a contradiction. In this case, you just need to return from the current recursion back.
If there are no contradictions and you put all 20 numbers, print the answer.
Otherwise, iterate over which number you put in the first unfilled point in a cycle. Put a number there and call it recursively.
It is only necessary to put the numbers already neatly placed in the picture in the right places. To do this, firstly, do not include them in the list of undelivered numbers, and secondly, put the number already written there in the filled positions.
Just iterating over all permutations (sets of arrays of numbers without repetitions) and checking the sums at the end, as you want to do, will be too long. There are 21 of them! (factorial) is too much.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question