CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 17 of 17

Thread: Find cartesians for matrix elements

  1. #16
    Join Date
    Feb 2017
    Posts
    608

    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.

  2. #17
    Join Date
    Feb 2017
    Posts
    608

    Re: Find cartesians for matrix elements

    I've had another look at this problem, and it seems to be a variation of the (exact) set cover problem:

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

    Here, the problem has the additional requirement that sets must form Cartesian matrixes. The problem is NP-hard, and so exact solutions for large input matrixes are intractable.

    For fun, I've implemented the algorithm I suggested in #16. I've kept step 1 as is. It requires 2^(n+m) iterations for an n times m input matrix. If m=n=10, there will be about 1 million iterations. It is still tractable but kind of the upper limit.

    Step 2 becomes intractable even for a 10 by 10 input matrix. So I follow the advice in the Wikipedia link above and replace step 2 with an approximate greedy algorithm. The Cartesian matrixes found in step 1 are sorted from larger to smaller. The algorithm then considers them one by one, and if a Cartesian matrix does not overlap with any other already in the solution, it is added to the solution. So the larger the Cartesian matrix, the sooner it will be considered for inclusion in the solution. This notion of "greediness" seems to work well and generate solutions very close to optimum (when the input matrix is split into the fewest Cartesian matrixes possible).


    Code:
    	#include <iostream>
    	#include <algorithm>
    	#include <ranges>
    	#include <utility>
    	#include <functional>
    	#include <string>
    	#include <array>
    	#include <vector>
    
    	void test() {
    		std::cout << "--- Test ---" << std::endl;
    
    		// Types
    
    		using Set = unsigned;	// a bitset
    		using CM = std::pair<Set,Set>;	// a Cartesian matrix (CM) is a <row-bitset, column-bitset> pair
    
    		// Helper functions
    
    		auto set_reverse = [](Set s, int n) { // reverse a Set s of n bits
    			Set r=0;
    			for (; --n >= 0; s >>= 1) r = (r <<= 1) | s&1;
    			return r;
    		};
    
    			// iterate the Set s and call the function f with the position of every 1-bit found 
    		auto set_scan = [](Set s, const std::function<void(int)>& f) {
    			for (int i=0; s!=0; s>>=1,++i) if ((s&1) != 0) f(i); 
    		};
    
    		auto set_count = [](Set s) { // count the 1-bits of the Set s
    			int i=0;
    			for (; s!=0; s>>=1) if ((s&1) != 0) ++i;
    			return i;
    		};
    
    		auto cm_string = [&] (CM cm) { // generate a string representation of a CM-pair
    			std::string s="", t="";
    			set_scan(cm.first, [&](int i) {s += char('A'+ i);});
    			set_scan(cm.second, [&](int i) {t += char('a'+ i);});
    			return s + ":" + t;
    		};
    
    			 // compare two CM-pairs and decide whether the first is greater than the second
    		auto cm_greater = [&] (CM cm1, CM cm2) {
    			return set_count(cm1.first)*set_count(cm1.second) > set_count(cm2.first)*set_count(cm2.second);
    		};
    
    		auto cm_overlap = [] (CM cm1, CM cm2) { // decide whether two CM-pairs overlap
    			for (Set r = cm1.first & cm2.first; r!=0; r >>= 1) {
    				if ((r&1) != 0 && (cm1.second & cm2.second) != 0) return true;
    			}
    			return false;
    		};
    
    		// The internal representation of the input matrix
    		// is an array of ROWS rows, each holding a bitset of COLS bits
    		// (A matrix has the 0 column to the left, whereas a bitset has the 0 bit to the right.
    		// Therefore the columns of the input matrix are reversed when represented with bitsets).
    		const int ROWS = 6;
    		const int COLS = 5;
    		std::array<Set, ROWS> input_matrix = { // example matrix 2 in post #1
    			set_reverse(0b01101, COLS),
    			set_reverse(0b01001, COLS),
    			set_reverse(0b11000, COLS),
    			set_reverse(0b11011, COLS),
    			set_reverse(0b10011, COLS),
    			set_reverse(0b00111, COLS)
    		};
    
    /*		const int ROWS = 4;
    		const int COLS = 4;
    		std::array<Set, ROWS> input_matrix = { // example matrix in post #10
    			set_reverse(0b0111, COLS),
    			set_reverse(0b0111, COLS),
    			set_reverse(0b0110, COLS),
    			set_reverse(0b1100, COLS),
    		};
    */
    
    
    		// Algorithm
    
    			// find all valid CMs of the input matrix
    		std::vector<CM> valid_CM;
    		for (Set r=1; r<(1<<ROWS); ++r) { // the full row powerset
    			for (Set c=1; c<(1<<COLS); ++c) { // the full column powerset
    				Set s=(1<<COLS)-1;
    				set_scan(r, [&](int i) {s &= input_matrix[i];});
    				if ((s&c) == c) {valid_CM.emplace_back(CM{r,c});}
    			}
    		}
    
    		std::ranges::sort(valid_CM, cm_greater); // sort valid CMs from larger to smaller CMs 
    
    		std::cout << "--- All possible CMs in sorted order from larger to smaller ---" << std::endl;
    		std::cout << "Number of CMs = " << valid_CM.size() << std::endl;
    		for (CM cm : valid_CM) std::cout << cm_string(cm) << std::endl; // print sorted CMs
    
    			// find approximate solution by selecting non-overlapping CMs greedily, 
    			// that is from larger to smaller
    		std::vector<CM> solution_CM;
    		for (CM new_cm : valid_CM) {	// all possible CMs sorted from larger to smaller 
    			bool no_overlap = true;
    			for (CM sol_cm : solution_CM) {
    				if (cm_overlap(sol_cm, new_cm)) {	// compare whether the new CM overlap
    					no_overlap = false;				// with any CM already in the solution
    					break;
    				}
    			}
    				// store the new CM if it is not overlapping with any CM already in the solution
    			if (no_overlap) solution_CM.push_back(new_cm); 
    		}
    
    		// Print the input matrix
    		std::cout << std::endl;
    		std::cout << "--- Input matrix ---" << std::endl;
    		std::cout << "  ";
    		for (int c=0; c<COLS; ++c) std::cout << char('a'+ c) << " ";
    		std::cout << std::endl;
    		for (int r=0; r<ROWS; ++r) {
    			std::cout << char('A'+ r) << " ";
    			Set s = input_matrix[r];
    			for (int c=0; c<COLS; ++c) {
    				std::cout << (((s&1) != 0) ? "1" : "0") << " ";
    				s >>= 1;
    			}
    			std::cout << std::endl;
    		}
    
    		// Print the solution CMs
    		std::cout << std::endl;
    		std::cout << "--- Solution CMs exactly covering the input matrix ---" << std::endl;
    		for (CM cm : solution_CM) std::cout << cm_string(cm) << std::endl;
    
    		std::cout << "--- End ---" << std::endl;
    		std::cout << std::endl;
    	} // test
    Last edited by wolle; Today at 03:34 AM.

Page 2 of 2 FirstFirst 12

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)