Items tagged with combinations

Feed

ma := allstructs(Permutation([1, 1, 1, 2, 2, 2, 3, 3, 3]), size = 3);

above is fast

but below is very slow.
ma2 := allstructs(Permutation(ma), size = 3);

just for all combinations of matrix , replicateM in haskell is the fastest.

in maple, ma2 := allstructs(Permutation(ma), size = 3); is very slow

 

I want to generate all 4x4 matrices of rank-1 over the field with two elements, F_2. I don't want to use actual arrays though, I just want to use symbols representing the unit matrices. So for example Eij represents the 4x4 matrix with a 1 in row i & column j, and 0's elsewhere. 

We have 16 unit matrices: E11, E12, ..., E14, ... E41, E42, E43, E44. Then we have to look at all possible linear combinations that result in a rank-1 matrix. So for example: E11+E12,  E11+E21,  E11+E12+E13,  E33+E43, etc. The total number of rank-1 4x4 matrices over F_2 is 225. How can I find all of these quickly?

how to permutate all combination of matrix of each element can only be 0,1,2

although it can be done in other language, and copy to maple

how to do this in maple with combinat package?

Hello!

I would like to start with the following set of 9 elements,
A = { E11, E12, E21, E22, E11+E12, E11+E21, E12+E22, E21+E22, E11+E12+E21+E22 }.

I need a procedure that takes each of those elements and creates 3 new ones in the following way: Eij becomes Eij1, Eij2, Eij1+Eij2. So for example, E11 will become: E111, E112, and E111+E112. And for example the fifth element in A (i.e. E11+E12) will become the 3 new elements: E111+E121, E112+E122, and E111+E121 + E112+E122.

Since each of the 9 elements gets triplicated, there will be a new set, call it B, with 27 elements.

B = {E111, E112, E111+E112, E121, E122, E121+E122, ... }

Now I want to repeat this process of triplicating again so that, for example, E111 becomes: E1111, E1112, and E1111+E1112. And so on. This new set C will have 81 elements. Now I want to repeat this one last time. The final set, D, will have 243 (3^5) elements. 

Step 2: 

For every pair of elements x and y in D, I want to compute z:=(x+y)mod2. If z already belongs to D, discard it, otherwise, place z in the set D2. Do this until there are no more elements to add together (note that if x+y is computed then I don't want y+x to be computed also--that's inefficient). Maybe the most efficient way is to perform all possibly combinations of x+y mod 2 to create the set D2 and then just go: D2 setminus D.

Step 3: For x in D and y in D2 perform all possible combinations of z:=(x+y)mod2 and place these in D3 then perform set subtraction again: D3 minus D2 minus D.

Repeat this process again: x in D and y in D3 to create new elements in D4. Repeat again until Dm is empty (that is, D(m-1) will be the last set that contains new elements). I'm expecting around 12 sets... 

The issue with this whole algorithm is that I often run out of memory so I need a clever way to do this, since this algorithm is essentially classifying 2^32 elements into disjoint sets. Thank you! 

I made a small change to the Task Filtering code I uploaded a few weeks ago.  The new code has better memory performance and, most importantly has more stable memory usage which means it can actually run very large examples.  Here is the new version of the code:

FilterCombPara := module( )
    local ModuleApply,
            doSplit,
            splitCombs,
            makeNewPrefix,
            lessThanX,
            filterCombs;

    lessThanX := proc( x, i ) x<=i; end;

    doSplit := proc( i::integer, prefix::set(posint), rest::set(posint),
                                                k::posint, filter::appliable, $ )
        splitCombs( prefix union {i}, remove( lessThanX, rest, i ), k-1, filter );
    end;

    splitCombs := proc( prefix::set(posint), rest::set(posint), k::posint,
                                                                filter::appliable, $ )
        if ( numelems( rest ) < k ) then
            NULL;
        elif ( k = 1 ) then
            filterCombs( prefix, rest, filter );
        else
            op( Threads:-Map( doSplit, rest, prefix, rest, k, filter ) );
        end;
    end;

    makeNewPrefix := proc( i, prefix ) { i, op( prefix ) } end;
    filterCombs := proc( prefix::set(posint), rest::set(posint), filter::appliable, $ )
        local i, f;

        op(select( filter, map( makeNewPrefix, rest, prefix ) )):
    end;

    ModuleApply := proc( n::posint, k::posint, filter::appliable, $ )
        [ splitCombs( {}, {seq( i,i=1..n )}, k, filter ) ];
    end;

end:

This code has the small mapping functions as module members instead of declared inline.  This means that less memory is churned as this code is excuted.  For a long runs, this helps keeps the memory stable.

As an example, I ran the following example:

> CodeTools:-Usage( FilterCombPara( 113,7, x->false ) );
memory used=17.39TiB, alloc change=460.02MiB, cpu time=88.52h, real time=20.15h
                                                  []

It used 88 CPU hours to run, but only 20 hours of real time (go parallelism!)  It used 17 Terabytes of memory, but only allocated 500 M.  This example is pretty trival, as the filter returned false for all combinations, so it did not collect any matches during the run.  However as long as the number of matches is small, that shouldn't be an issue.  If the number of matches is too large to fit in memory, then this code may need to be modified to write the matches out to disk instead of trying to hold them all in memory at once.

Darin

-- Kernel Developer Maplesoft

FilterComb.mw

This blog post is a response to a post on MaplePrimes.  MaplePrimes user wkehowski asked how the Task Model could be used to filter combinations.  The basic problem is formalated like this:  We want a function, I'll call it FilterComb, that accepts positive integers...

Hi,

I'm trying to generate all the possible combinations of each M[i] according to the possible values for c,d and e. The code I have here generates some of them but not all - it misses out the combinations when the two or three elements in the square brackets are different ie. 

it generates
[{1}, [{1}, {1}], [{1}, {1}, {1}]]               
[{1}, [{2}, {2}], [{2}, {2}, {2}]]             

I'm very new to Maple and can't figure out how to do this:

I have these possibilities:

for 1 - [1],[2],[3]

for 2 - [1,2],[2,1],[1,3],[3,1],[2,3],[3,2]

for 3 - [1,2,3],[2,3,1],[3,1,2],[3,2,1],[2,1,3],[1,3,2]

and I want to find all the possible combinations when they are in, say, the order of [3,2,1]

eg.

[[1,2,3],[1,2],[1]],

[[1,2,3],[1,2],[2]],

[[1,2,3],[1,2],[3]], 

[[1,2,3],[2,1],[1]]

So, I have a list of vectors v1,...v8 - and I want to consider all {0,1}v1 + {0,1}v2+ ... + {0,1}v8 (I need a list of all 2^8 possible combinations). 

 

I can run 8 simple for loops and use the mod command, but that's inconvenient. Is there a nice way to do what I'm trying to get done? 

I am looking to create a list-of-lists with all the combinations of 1..7.
The order is not important so for example [1,7] [7,1] should only return [1,7]

ie

[[1],[2],[3],[4],[5],[6],[7],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],

[2,2], [3,3], [4,4] ......................
[3,2]...................
.......
[7,2].............

[1,2,1]........

[1,2,2].......     ]

 

I am no sure I am explaining...

Page 1 of 1