I will not find the algorithm. There is a two-dimensional array of D (unlimited rows, n columns known, but may vary). There is an array M of m elements. How to get all possible options for filling D elements M , provided that the element D[i,j] can be filled only if the element D[i-1,j] filled?

As an example. Let n=4 , m=3 , M = {m1, m2, m3} ? Then we can fill D , for example:

 {m1, , m2, m3} {d1, d2, d3, d4} - это просто индексы столбцов D или {m3, , , } {m1, , m2, } {d1, d2, d3, d4} но нельзя делать так (т.к. элемент m3 "оторван" получается) { , m3, , } {m1, , m2, } {d1, d2, d3, d4}

Is there any algorithm for getting all possible fill combinations?

    1 answer 1

    I suspect that the easiest way to do this is to do a recursive function. You go along array D from left to right, from top to bottom (as if reading a book), and in each cell D either leave an empty space, or take the next number for M from M , and one that has not been taken yet which notes which elements have already been taken and which are not). Having placed the next element (or without putting anything), proceed to the next position D In this case, of course, check whether it is possible to put an element according to your condition (that something is placed on top, or this is the first line). Of course, hardly anyone will write a program.

    • I will write the program myself, this is no problem. The problem is with the algorithm. In your recommendation, this is just an algorithm for random filling, as I understand it (I accidentally determine whether a cell is filled in or not, and an arbitrary element of M). And I need ALL possible fill combinations. How to do it? - Victor
    • I wrote exactly how to get ALL possible combinations. It is not by chance that we determine whether to fill the cell or not, and in the cycle we iterate over all possible characters and put them in the cell in turn, recursively moving on to the next one. - Zealint
    • it is possible then more detailed. "either you leave an empty space, or you take the next number from M for this place" - how to formalize this rule "either"? And what algorithm to take a number from M? After all, there are several elements and in what order do we take the same value? - Victor
    • I am afraid that if you do not know what recursion is, you will not understand my explanation. Everything is very simple here: being at a certain position (i, j), we iterate over all the numbers in the array M (in any order) in the loop. Putting the next number in the position (i, j), go to the position (i, j + 1) and do the same there. Of course, you need to check when you can put a number, and when not. You also need to check that the next number that we want to deliver, was not delivered earlier somewhere. If this explanation is incomprehensible, but I cannot help you anymore, you should first study recursion. - Zealint
    • What is recursion is quite familiar to me. I do not see in your algorithm an element of randomization of something (which, in this case, will ensure that all combinations are repeated). Your explanation says "either set or not." What rule defines this "either" for a specific recursion step? - Victor