How can I generate the kind of truth table described below?

Hi, I am having an issue trying to generate this kind of truthtable:

every letter indicates a specific device that it can have 2 or more states, and every device can have just one state active (not two or more active states at the same time):

In this example we have the device a with 2 states and the device b with 3 states, I want to write a script giving just this informations and generate a matrix like this: (with just one and zeros, obviously without a_0 a_1 b_0 b_1 b_2)

 a_0  a_1  b_0  b_1  b_2

   1    0    1    0    0    
   1    0    0    1    0
   1    0    0    0    1
   0    1    1    0    0
   0    1    0    1    0
   0    1    0    0    1

As you can see every device has only one active state in every combination, I need to generalize this process to an arbitrary number of devices everyone with an arbitrary number of states, and generating all possible combinations with the retrictions that i described above. Thank you very much for your help.

[Star Strider]

In my understanding of truth tables, you have to have inputs corresponding to the outputs. The table you posted is a ‘sort of’ output table. What are the inputs to ‘a’ and ‘b’, and how are the interconnections (if any) between ‘a’ and ‘b’ defined?

[simone clochiatti]

Simply the inputs are the number of possible states of every device, in the example the devices are a and b, so the inputs should be 2 states for the device a and 3 states for the device b; with this two numbers I want to generate the table above.

[Star Strider]

Still, it’s not a truth table in the conventional sense I’m familiar with. You’re just defining states, sort of like writing to a register. All you have to do is to set the appropriate states and be sure only one is selected at a time.

[simone clochiatti]

exatly that is, but pratically how can you manually set every possible combination of states of every device if there are too many and with many states for each one?

Answer 1

[Walter Roberson]

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} = toeplitz([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));

The code optimizes by only creating the unique subtables -- e.g., in the above example the third device has 2 entries just like the first device does, and it is not necessary to build the sliding 1 table multiple times.

Construction of the sliding 1 table could be done incrementally from smallest to largest but it is not clear it would be any faster than the clearer method of calling toeplitz once per size.

The output order might not be exactly how you would prefer, but the list is exhaustive.

[simone clochiatti]

Yes! It works perfectly, thank you very much! The problem is that I have tried to understand your code until now; I am new to Matlab programming, while I was reading your script I understood what the cell-array are, I think that are the ones in which you use the curly brakets. I ask you another favour: could you be so kind to comment a little bit your code? so I will understand it, this is very important for me. Thank you another time for your help.

[Image Analyst]

I believe the FAQ has a good description of cell arrays http://matlab.wikia.com/wiki/FAQ#What_is_a_cell_array.3F such as telling you when to use braces and when to use parentheses.

[simone clochiatti]

Excuse me, just one question: why in the for cycle you use:

   state_tables{K} = toeplitz([1, zeros(1,uniq_numstates(K)-1)]);

instead of simply writing:

state_tables{K} = diag(ones(1,uniq_numstates(K)));

It generates the same square matrix with the ones on diagonal.

[simone clochiatti]

Thank you Image Analyst, I used that FAQ and I understood the concept of cell-array, now the problem for me is only the last 3 rows of the code which are not clear for me.

[simone clochiatti]

P.S: the mistery for me is what the square brackets mean in this row of code:

    [idxgrid{1:length(numstates)}] = ndgrid(idx_list{ic});

I understands what ndgrid does and what it produces, but I cant understand how this elements are assigned in the left expression with square brackets.

[Walter Roberson]

I used toeplitz instead of diag because I didn't think of diag ;-)

The ndgrid call I coded uses advanced features.

ndgrid(idx_list{ic}) is the same as if you had coded

ndgrid(idx_list{ic(1)}, idx_list{ic(2)}, idx_list{ic(3)}, .... idx_list{ic(end)})

all as individual arguments, except that you do not need to know the exact number ahead of time like you would if you coded them yourself.

The {} expansion works exactly the same way on the left side of the "=". The left side is as if you had coded

[idxgrid{1}, idxgrid{2}, idxgrid{3}, ... idxgrid{length(numstates)}] = ndgrid(idx_list{ic});

That is, ndgrid is asked to create length(numstates) outputs and put them in idxgrid{1}, idxgrid{2}, idxgrid{3}, ... idxgrid{length(numstates)}

ndgrid() does not have a fixed number of outputs like meshgrid does -- meshgrid must have 0, 1, or 2 outputs but ndgrid can have any number. An array is created for each output, so in this case length(numstates) different arrays would be created.

[simone clochiatti]

Thank you, I understood how it works, I still have problems on the last 2 rows of the code, in cell2mat I expected to have a function in the first element, but what does it mean @(C) C(:) ?? I checked in the documentation but I cant find anything, another problem that I have is with the function ndgrid (I have studied how it behaves,but is still not clear for me how you use it in this problem) It is strange because the main part of the code is very simple for me, and I feel to guess why you generate the digonal matrix; but the last three rows of code are completely unknown for me. Is it possible to simplify that 3 rows of code? making them more suitable for a beginner? I dont know if the problem for me is understanding the code or is just that I dont understand how you generate the table from that multiple diagonal matrix's you create by using the for cycle. Thank you so much for your help.

[Walter Roberson]

If you had an array C, then C(:) reshapes the contents into a single column vector, exactly the same as reshape(C, [], 1)

@(C) C(:) is an anonymous function that when called with an argument, returns the argument reshaped as a column vector.

cellfun(@(C) C(:), idxgrid, 'uniform', 0)

goes through the cell array "idxgrid" and calls @(C) C(:) on the contents of each entry in the cell array, the same as if you had used

reshape_fun = @(C) C(:);
idxlist = cell(size(idxgrid));
for K = 1 : numel(idxgrid)
   idxlist{K} = reshape_fun(idxgrid{K});
end

That is, each entry in the cell array idxgrid is a multidimensional array returned by ndgrid, and the code goes through and makes column vectors out of each of the entries. For example,

{[1 2; 3 4], [5 6; 7 8]}

would become

{[1;3;2;4], [5; 7; 6; 8]}

(Notice that reshaping into column vectors goes down the columns, not across the rows.)

I will describe the logic of the cell2mat() call after I have done some yard work.

Answer 2

[Image Analyst]

I don't think there's anything that does exactly that, so you might have to play around a little bit with the perms() function, or maybe meshgrid().

[simone clochiatti]

Thank you for your advice, but sorry I tryed until now with perms and I cant find a solution: I have generated this vector:

0 1 0 1 0 1 0 0 0 1

this means 3 devices with 2 states ( the first 6 elements) and 1 device with 4 possible states (the last 4 elements) then I have generated a matrix with all possible permutations using perms. Now I am trying an approach to eliminate the rows of that matrix with the ones in the wrong position such as:

1 1 0 1 1 0 0 0 0 0 (because the device 1 have the 2 states active at the same time, and is impossible that the device 4 has none active states)

0 1 1 1 1 0 0 0 0 0 (because the device 2 have the 2 states active at the same time, and is impossible that the device 4 has none acrive states)

1 0 0 0 1 0 0 1 1 0 (because the device 4 has two states active at the same time, and of course is impossible that the device 2 has the 2 states off at the same time)

I have the matrix and now the problem is to eliminate all the kind of rows that I described above. I will be so glad of you could help me, thank you.