1 Attachment(s)
algorithm for grouping different elements from multi dimensional matrix
Attachment 33305
Hi fellow coders
I have a question in regards to an algorithm problem I am trying to solve.
The input data to the algorithm is a matrix that can be described as follows:
The matrix has N dimensions, like the one in the attached picture (which has 2 dimensions for example).
There are a number of elements (denoted as c1, .. c5 in the attached sample matrix) that are mapped into the cells of the matrix.
An element can occur in one or more cells in the matrix.
The algorithm should work as follows:
Pick (and then remove) elements from the matrix and group them into buckets of E elements, so that:
1. the elements in each bucket don't have any common values on any of the dimensions
2. each element is assigned only into one bucket
For example, referring to the sample matrix attached, if we selected E to be 2, then a possible grouping could be: {c1, c2} ; {c3, c4} and {5} by itself. Check: c1 and c2 (and c3 and c4) don't have any common column or row values in the matrix.
The problem has been doing my head in for some time now and I thought it may be worth asking if some whiz here has a solution.
Thanks
Re: algorithm for grouping different elements from multi dimensional matrix
as it is formulated, the problem solution seems not depending on the initial configuration, IOW, it's equivalent to finding *any* disposition of elements satisfying 1. and 2. in a given *empty* M1xM2x...xMN matrix; this is confusing because you started by saying that some elements are initially mapped in the matrix ... is this the intent ?
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
superbonzo
as it is formulated, the problem solution seems not depending on the initial configuration, IOW, it's equivalent to finding *any* disposition of elements satisfying 1. and 2. in a given *empty* M1xM2x...xMN matrix; this is confusing because you started by saying that some elements are initially mapped in the matrix ... is this the intent ?
Yes, the intent is that the input to the algorithm is a mxmxm...xm matrix, in which each cell is either :
1. Empty, ie no elements; or
2. Contains one or more elements.
Does this clarify the problem?
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
ahlandberg
Does this clarify the problem?
not much; let's clarify, you said
1) "an mxm...xm matrix", so are all dimension the same ? ( you initial example was not )
2) "group them into buckets of E elements", but then you group "c5" into a single element bucket; do you mean that buckets should have *at most* E elements ?
3) initially the matrix has repeated elements ( c5 appears twice ) but then you remove a c5 in your grouping example; so, can we remove as many element repetitions as we like ? this is confusing because, if it were true, the solution would be trivial ..
sorry, but you have to define the problem formally before we can formulate an algorithm ...
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
superbonzo
not much; let's clarify, you said
1) "an mxm...xm matrix", so are all dimension the same ? ( you initial example was not )
2) "group them into buckets of E elements", but then you group "c5" into a single element bucket; do you mean that buckets should have *at most* E elements ?
3) initially the matrix has repeated elements ( c5 appears twice ) but then you remove a c5 in your grouping example; so, can we remove as many element repetitions as we like ? this is confusing because, if it were true, the solution would be trivial ..
sorry, but you have to define the problem formally before we can formulate an algorithm ...
Re 1) yes it is a k x l x m x n ... Matrix where any dimension can have an arbitrary siZe. For example 5 x 100 x 2.
Re 2) yes at most E elements. In my example c5 is a leftover elements that just happens to go into its own group.
Re 3) yes it can have repeated elements. But , when we remove one of the elements from the matrix (which have repetitions), then all those repetitions must be removed from the matrix. But the element itself (eg c5) only is mapped into one single group.
Thank you for working with me on this. Hope it clarifies.
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
ahlandberg
if some whiz here has a solution.
Well, this problem looks like a set cover problem and in that case it's in NP. This means any polynominal "whiz" solution can only be approximate. But the problem can still be solved of course only it becomes intractable when big. Here's a naive combinatorial approach.
The problem has a certain mutiplicity since any c can appear several times. In your example c5 appears two times so it has multiplicity 2. All other c:s have multiplicity 1 since each appear once only. If the multiplicity of all c:s are multiplied you get the total multiplicity which in your example is M = 1*1*1*1*2 = 2.
Now lets split the problem into M problems each with M=1. It means there are no multiple occurances of any c in any of these problems. It also means we have to solve M problems. This takes care of your rule 2.
We now define the bucket compatibility BC. All c:s in a bucket must be BC. This simply is your rule 1. To ensure BC every c in a bucket must be pairwise BC with every other c in the same bucket. Pairwise BC is easy to check. It's when two c:s have not index in common in any dimension.
The algorithm:
1. We have an initial set S of all c:s like {c1,c2,c3,c4,c5}. We now generate all possible first buckets. This means we extract all E-subsets of the S set. In your example E=2. We only consider E-subsets that are BC.
2. We then proceed with all possible next buckets for every previous bucket. The E c:s of the previous bucket is removed from S so for each next bucket S becomes E c:s less.
3. This continues bucket by bucket until S contains less than E c:s. If S is BC we have a
solution.
This is a typical branch-and-bound algorithm. It builds a tree (typically using recursion) where each level represents a new bucket being added (the branching). If a bucket is found not to be BC this path of the tree is not pursued further down (the bound). When a leaf is reached all c:s are in buckets and we have a solution.
This algorithm must be repeated for each of the M multiplicities.
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
razzle
Well, this problem looks like a set cover problem and in that case it's in NP. This means any polynominal "whiz" solution can only be approximate. But the problem can still be solved of course only it becomes intractable when big. Here's a naive exhaustive combinatorial approach.
The problem has a certain mutiplicity since any c can appear several times. In your example c5 appears two times so it has multiplicity 2. All others have multiplicity 1 since they appear only once. If the multiplicity of all c:s are multiplied you get the total multiplicity which in your example is M = 1*1*1*1*2 = 2.
Now lets split the problem into M problems each with M=1. It means there are no multiple occurances of any c in any of these problems. It also means we have to solve M problems. This takes care of your rule 2.
We now define the bucket compatibility BC. All c:s in a bucket must be BC. This simply is your rule 1. To ensure BC every c in a bucket must be pairwise BC with every other. Pairwise BC is easy to check. It's when two c:s have not index in common in any dimension.
The algorithm:
1. We have an initial set S of all c:s like {c1,c2,c3,c4,c5}. We now generate all possible first buckets. This means we extract all M-subsets of the S set. In your example M=2. We only consider M-subsets that are BC.
2. We then proceed with all possible next buckets for every previous bucket. This time the M c:s of the previous bucket have been removed from S.
3. This continues bucket by bucket until S contains less than M c:s. If S is BC we have a
solution.
This is a typical branch-and-bound algorithm. It builds a tree (typically using recursion) where each level represents a new bucket being added (the branching). If a bucket is not BC this path of the tree is not pursued (the bound). When a leaf is reached (all c:s are in buckets) we have a solution.
This algorithm must be repeated for each of the M multiplicities.
Thanks , it makes sense but I need to let it sink in ....
I had read about this type of problem in a research paper on "multi sensitive bucketisation" that claimed its algorithm is O(n). I can't read most of the paper because it's in Chinese. But I google translated the algorithm and it read too simplistic and not detailed at all. I also think this probes has no trivial solution or linear solution.
Re: algorithm for grouping different elements from multi dimensional matrix
Quote:
Originally Posted by
ahlandberg
Thanks , it makes sense but I need to let it sink in ....
Sure, the algorithm I suggested will solve the problem but not necessarily in the most efficient way. Also there are quite a few details left such as for example,
1. How to check for BC in the most efficient manner for big buckets and lots of dimensions.
2. How to efficiently generate all BC E-subsets (*) of an S set.
Feel free to ask. Good luck!
(*) I mistakingly called it an M-subset in my first reply but I've corrected that. It should be E-subset where E is the size of a bucket.
