CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 18

Threaded View

  1. #15
    Join Date
    Feb 2017
    Posts
    621

    Re: Find cartesians for matrix elements

    Quote Originally Posted by JackK View Post
    But the problem is that the algorithm is unknown to me yet.
    I thought that it's maybe known to some of you.
    You can always apply exhaustive combinatorics:

    1. Systematically generate all Cartesian matrixes that may occur in any matrix the size of the input matrix. Select those that are present in the input matrix.

    2. Systematically generate all possible combinations of the Cartesian matrixes selected in 1. Select the valid combinations, that is where the sum of the Cartesian matrixes without overlapping matches the input matrix exactly.

    3. Out of all valid combinations found in 2, select the combination(s) with the fewest Cartesian matrixes. That's it!

    There are 2^(n+m) possible Cartesian matrices in an n*m input matrix, so step 1 is only feasible for small matrixes. The feasibility of step 2 depends on how many Cartesian matrixes there actually are in the input matrix. If there are k, there will be 2^k possible combinations, so also the number of combinations becomes intractable very fast. But still, this algorithm will work, and that's better than having nothing.

    Both steps 1 and 2 involves generating the powerset of a set,

    https://en.wikipedia.org/wiki/Power_set

    Good luck!
    Last edited by wolle; July 20th, 2021 at 01:20 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured