Unique Permutation: with logical Elements OR with vectors which should at the end stand as one dimension (after each other) in a 2-dim-Matrix

Hello everybody,

I have a tough problem. I try to explain in a simple way: I need a logical 2-dim-matrix (just ones and zeros) with every possible combination of ones and zeros AND some additional conditions:

• number of "ones" per line is fixed, e.g. two "ones" per line, but it can be more. Variable "N_min" shows the exact number of ones per line
• some columns (always side by side) refer to each other and in these columns, there must be at most one "one" per line. Number of columns, which refer to each other, may change between one and ... well, open end. Also 100 columns is possible. The vector "NoL" indicates, how many columns refer to each other.

Here is an example. NoL and N_min are known, X is what i am looking for:

NoL = [1 3 3]
N_min = 2

X=[
0 0 0 1 0 0 1;
0 0 0 1 0 1 0;
0 0 0 1 1 0 0;
0 0 1 0 0 0 1;
0 0 1 0 0 1 0;
0 0 1 0 1 0 0;
0 1 0 0 0 0 1;
0 1 0 0 0 1 0;
0 1 0 0 1 0 0;
1 0 0 0 0 0 1;
1 0 0 0 0 1 0;
1 0 0 0 1 0 0;
1 0 0 1 0 0 0;
1 0 1 0 0 0 0;
1 1 0 0 0 0 0]

NoL indicates, that the first column stands alone for itself, columns 2-4 and 5-7 refer to each other and in these columns, there must be at most one "one" per line, but could be all zero after all. N_min means, there are 2 "ones" in every line.

Until now i did it the following way (and it works fine until the matrix grows too large): I made a vector w and used "uperm" from Bruno Luong (<http://www.mathworks.com/matlabcentral/newsreader/view_thread/164470)>, then i deleted every line where my second condition is violated. Refered to my example at top:

w = [1 1 0 0 0 0 0]
W = uperm(w)
X = deletesomelines(W,NoL) %"deletesomelines" is a function written by myself to delete every line which violates the rule of just one "one" per line in refering columns

Problem is: with bigger Matrizes my PC keeps on running out of memory. Last thing that worked was a vector w with seven "ones" and 28 "zeros". uperm generated a Matrix with 35 columns and about 7 million lines. My PC was out of memory. And this is not the upper end of matrix sizes i want to work with.

My thoughts of solution:

a) Can someone please help me by converting the uperm-function of Bruno Luong into a logical function which uses just logical expressions instead of doubles? 35x7mio Matrix of datatype "double" needs 2GB, of type "logical" just 25 MB

b) Has anybody an idea of a special function for my problem? A "permutation of permutations" to directly get just the matrix i need instead of getting a very big one and deleting many lines?

[James Tursa]

Do you have a C compiler? This might be an interesting problem for me to attack with a mex routine.

[Andreas Peter]

I'm sorry, but as a result of working on a PC of my university there is no c-Compiler on it and i have no chance to get it on the PC.

Answer 1

[Thorsten]

This generates your example; you may generate the other matrices accordingly.

 N = 3;
 m = logical(fliplr(eye(N)))
 m1 = reshape(repmat(m, N, 1), N, [])'
 m2 = repmat(m, N, 1)
 m0 = logical(ones(N^2, 1)); m0 = [~m0; m0];
 M = [m0 m1 m2];

Answer 2

[Walter Roberson]

http://www.mathworks.com/matlabcentral/answers/237767-how-can-i-generate-the-kind-of-truth-table-described-below

[Andreas Peter]

I'm sorry but you didn't get the problem. My problem is: Matlab runs out of memory. I need the truthtable as a logical table directly. Your code gives me a "double"-Matrix, which needs way too much RAM (See my example above, 2.000 MB instead of 25MB)

Second disadvantage of your proposed code is, that there are always as many ones in a line as number of subtables, but i usually need less than this. The number of ones per line is definded by "N_min".

Can you please modify your code? In my opinion it would be enough if you insert a new line in every subtable with all zeros and make the truthtable a logical table (not double). I will afterwards delete every line with more or less ones than N_min.

I tried to do this but i failed. I have never worked with cell arrays before and i do not get the point of all these functions you used (ndgrid, toeplitz, arrayfun, ic etc.)

[Walter Roberson]

Adjusted to use logical instead of double, but not yet adjusted for number of ones per line:

numstates = [2, 3, 2];          %three device example

num_orig = length(numstates);

[uniq_numstates, ~, ic] = unique(numstates);
num_uniq = length(uniq_numstates);
state_tables = cell(num_uniq,1);
idx_list = cell(num_uniq,1);
for K = 1 : num_uniq
  state_tables{K} = logical(toeplitz(uint8([1, zeros(1,uniq_numstates(K)-1)])));
  idx_list{K} = 1:uniq_numstates(K);
end
[idxgrid{1:length(numstates)}] = ndgrid(idx_list{ic});
idxlist = cellfun(@(C) C(:), idxgrid, 'uniform', 0);

truth_table = cell2mat(arrayfun(@(K) state_tables{ic(K)}(idxlist{K},:), 1:num_orig, 'uniform',0));

[Andreas Peter]

Thank you. I will try this code with some more cases but first tries seemed very good. To adjust it for "number of ones per line" i added some new stuff:

In the loop i added

state_tables{K}(end+1,:)=0;
idx_list{K}(end+1) = idx_list{K}(end)+1;

This adds a line in the subtables with all zero. At the end of your code I added two more code-lines to clear all lines with more or less ones than supposed:

idxclear = find(sum(truth_table') ~= N_min);
truth_table(idxclear,:) = [];

So now its working like i want it to. I just have to check whether it's also working for bigger matrices. Thank You!

[Guillaume]

@Walter, I'm not sure I understand the use of

logical(toeplitz(uint8([1, zeros(1,uniq_numstates(K)-1)])))

to generate an identity matrix. Wouldn't

logical(eye(uniq_numstates(K), 'uint8'))

be a lot clearer and possibly faster?