1
$\begingroup$

Given is a list of numbers.

Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is equal to the sum of numbers from any point of another row to the end/beginning.

E.g.

    • $1,2,3,4$
    • $2,3,4,1$
    • $4,3,1,2$

is allowed, while

    • $1,2,3,4$
    • $2,3,4,1$
    • $4,3,2,1$

or,

    • $1,2,3,4$
    • $2,3,4,1$
    • $3,4,2,1$

isn't because, in (2) $2+3+4$ in the second row $= 4+3+2$ in the third and,

in (3) $1+2$ of the first row $= 3$ of the third (analog $1 = 1$ or $3+4 = 4+2+1$ if you add the numbers in the opposite direction)).

What would be an appropriate algorithm to determine the maximum number of permutations fulfilling that criteria and print out one solution with that many permutations? Is some kind of greedy algorithm useful here, or can we somehow construct a graph out of that problem?

Until now I have only some brute force algorithms for solving the problem. Thanks for any tips on the algorithm in advance :)

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Is the size of of the matrix (number of rows, length of each row) specified as part of the input? And what's the context where you encountered this problem? Can you credit the source? $\endgroup$ – D.W. Feb 11 '18 at 1:30
  • $\begingroup$ it is specified partly: there is a list of numbers given (so the length of each row since every number has to be part of each row), and out of that you can just calculate the maximum of rows (summ of all numbers / (number of the numbers - 1) but as simplification you can presume there are only numbers from 1 to n with a given n $\endgroup$ – L.Hansen Feb 11 '18 at 10:50
  • $\begingroup$ So each row has to be a permutation of the numbers in the original list? We can choose any number of rows we want? ould it be OK if the output has only one row (even though it might be possible to add more rows)? $\endgroup$ – D.W. Feb 11 '18 at 16:39
  • $\begingroup$ Yeah, each row is a permutation of the original list that contains each number of it exactly once. The task of the algorithm is to determine the max number of rows and display a solution with that many rows. (Sorry for being so vague in the explanation of the problem, I hope everything is clear now) $\endgroup$ – L.Hansen Feb 11 '18 at 17:17
  • $\begingroup$ Can you edit the question to incorporate this information into the problem statement? I don't see that stated in the question. We want questions to be complete and stand on their own, so that people don't need to read the comments to understand what you are asking. Rather than leaving clarifications in the comments, we ask that you edit the question so it will be clear to someone who encounters it for the first time. Thank you! Also, can you tell us teh context where you encountered this, and credit the source of the problem? $\endgroup$ – D.W. Feb 11 '18 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.