2
$\begingroup$

Say I have a list

List1={
      {1, *, *, *}, {*, 1, *, *}, {*, *, 1, *}, {*, *, *, 1}, 
      {0, *, *, *}, {*, 0, *, *}, {*, *, 0, *}, {*, *, *, 0} 
      }   

Let intersection function meet(a,b) is the function of two variables $a$ and $b$ from the list List1$\times$List1 (the elements of List1 themselves are lists of equal length); The function should do the following:

IF there is no $i$ with ($a_i=1$ and $b_i=0$) OR ($a_i=0$ and $b_i=1$)

then meet(-,-) adds as an element (by Union[-,-])to the List1
the list $m$ of the same length as $a$ and $b$, such that for each $i$

If ($a_i=1$ and $b_i=*$) OR ($a_i=*$ and $b_i=1$) OR ($a_i=1$ and $b_i=1$) then $m_i=1$,

else if ($a_i=0$ and $b_i=*$) OR ($a_i=*$ and $b_i=0$) OR ($a_i=0$ and $b_i=0$) then $m_i=0$,

else (if we have $a_i=*$ and $b_i=*$) $m_i=*$

ELSE (i.e. if there is $i$ with $a_i=1$ and $b_i=0$ OR $a_i=0$ and $b_i=1$)

adds nothing to the List1 (does nothing).

I want to iterate meet(-,-) on the List1 to add all such intersections until the operation terminates.

In particular the intersection of two elements of List1

{1, *, *, *} 

and

{*, 1, *, *} 

is as described above a list (an element)

{1, 1, *, *} 

since this element is not yet in List1, then meet({1, *, *, },{, 1, *, *}) adds this element to the List1

while

{1, *, *, 0}

and

{*, 1, *, 1}

have no intersecton (since on 4th place we have 0 and 1 respectively) and hence the function adds nothing to the List1

Finally I want to have List1 equal to

{
 {1, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 1, *}, {1, 1, 0, 1}, {1, 1, 0, 0}, {1, 1, 0, *}, 
 {1, 1, *, 1}, {1, 1, *, 0}, {1, 1, *, *}, {1, 0, 1, 1}, {1, 0, 1, 0}, {1, 0, 1, *}, 
 {1, 0, 0, 1}, {1, 0, 0, 0}, {1, 0, 0, *}, {1, 0, *, 1}, {1, 0, *, 0}, {1, 0, *, *}, 
 {1, *, 1, 1}, {1, *, 1, 0}, {1, *, 1, *}, {1, *, 0, 1}, {1, *, 0, 0}, {1, *, 0, *}, 
 {1, *, *, 1}, {1, *, *, 0}, {1, *, *, *}, {0, 1, 1, 1}, {0, 1, 1, 0}, {0, 1, 1, *}, 
 {0, 1, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, *}, {0, 1, *, 1}, {0, 1, *, 0}, {0, 1, *, *}, 
 {0, 0, 1, 1}, {0, 0, 1, 0}, {0, 0, 1, *}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, *}, 
 {0, 0, *, 1}, {0, 0, *, 0}, {0, 0, *, *}, {0, *, 1, 1}, {0, *, 1, 0}, {0, *, 1, *}, 
 {0, *, 0, 1}, {0, *, 0, 0}, {0, *, 0, *}, {0, *, *, 1}, {0, *, *, 0}, {0, *, *, *}, 
 {*, 1, 1, 1}, {*, 1, 1, 0}, {*, 1, 1, *}, {*, 1, 0, 1}, {*, 1, 0, 0}, {*, 1, 0, *}, 
 {*, 1, *, 1}, {*, 1, *, 0}, {*, 1, *, *}, {*, 0, 1, 1}, {*, 0, 1, 0}, {*, 0, 1, *}, 
 {*, 0, 0, 1}, {*, 0, 0, 0}, {*, 0, 0, *}, {*, 0, *, 1}, {*, 0, *, 0}, {*, 0, *, *}, 
 {*, *, 1, 1}, {*, *, 1, 0}, {*, *, 1, *}, {*, *, 0, 1}, {*, *, 0, 0}, {*, *, 0, *}, 
 {*, *, *, 1}, {*, *, *, 0}
}

What is a efficient way to do such expansion of an initial list List1 effectively in Wolfram Mathematica?

$\endgroup$
  • 2
    $\begingroup$ I must admit, I've reread this a few times and I'm not 100% sure what the operation we're trying to achieve here is. $\endgroup$ – user6014 Aug 27 at 18:48
  • $\begingroup$ Ok I'll try to clarify the question. $\endgroup$ – Evgeny Kuznetsov Aug 27 at 19:03
  • $\begingroup$ what is the desired result for List2={{1, "*", "*"}, {"*", 1, "*"}, {"*", "*", 0}}? $\endgroup$ – kglr Aug 27 at 19:39
  • $\begingroup$ I made changes, if someone helps me to write down the desired code I will be appreciate, I realize what to do but do not know how to do it in a proper way. $\endgroup$ – Evgeny Kuznetsov Aug 27 at 20:42
  • $\begingroup$ What is the intersection of {1, *, *, 1} and {*, 1, *, 0}? $\endgroup$ – user6014 Aug 27 at 21:04
3
$\begingroup$
ClearAll[f, g, h]
f["*", a_] := a
f[a_, "*"] := a
f[a_, a_] := a
f[a_, b_] /; a != b := "*"

SetAttributes[f, Listable]
g = DeleteCases[DeleteDuplicates[f @@@ Tuples[#, {2}]], {"*" ..}] &;

h = FixedPoint[g, #]&

(You can also use Nest[h, #, 2]&.)

Example:

Input list from OP:

List1 = {{1, "*", "*", "*"}, {"*", 1, "*", "*"}, {"*", "*", 1, 
    "*"}, {"*", "*", "*", 1}, {0, "*", "*", "*"}, {"*", 0, "*", 
    "*"}, {"*", "*", 0, "*"}, {"*", "*", "*", 0}};

Desired output from OP:

List2 = {{1, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 1, "*"}, {1, 1, 0, 1}, {1,
    1, 0, 0}, {1, 1, 0, "*"}, {1, 1, "*", 1}, {1, 1, "*", 0}, {1, 1, 
   "*", "*"}, {1, 0, 1, 1}, {1, 0, 1, 0}, {1, 0, 1, "*"}, {1, 0, 0, 
   1}, {1, 0, 0, 0}, {1, 0, 0, "*"}, {1, 0, "*", 1}, {1, 0, "*", 
   0}, {1, 0, "*", "*"}, {1, "*", 1, 1}, {1, "*", 1, 0}, {1, "*", 1, 
   "*"}, {1, "*", 0, 1}, {1, "*", 0, 0}, {1, "*", 0, "*"}, {1, "*", 
   "*", 1}, {1, "*", "*", 0}, {1, "*", "*", "*"}, {0, 1, 1, 1}, {0, 1,
    1, 0}, {0, 1, 1, "*"}, {0, 1, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 
   "*"}, {0, 1, "*", 1}, {0, 1, "*", 0}, {0, 1, "*", "*"}, {0, 0, 1, 
   1}, {0, 0, 1, 0}, {0, 0, 1, "*"}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 
   0, 0, "*"}, {0, 0, "*", 1}, {0, 0, "*", 0}, {0, 0, "*", "*"}, {0, 
   "*", 1, 1}, {0, "*", 1, 0}, {0, "*", 1, "*"}, {0, "*", 0, 1}, {0, 
   "*", 0, 0}, {0, "*", 0, "*"}, {0, "*", "*", 1}, {0, "*", "*", 
   0}, {0, "*", "*", "*"}, {"*", 1, 1, 1}, {"*", 1, 1, 0}, {"*", 1, 1,
    "*"}, {"*", 1, 0, 1}, {"*", 1, 0, 0}, {"*", 1, 0, "*"}, {"*", 1, 
   "*", 1}, {"*", 1, "*", 0}, {"*", 1, "*", "*"}, {"*", 0, 1, 
   1}, {"*", 0, 1, 0}, {"*", 0, 1, "*"}, {"*", 0, 0, 1}, {"*", 0, 0, 
   0}, {"*", 0, 0, "*"}, {"*", 0, "*", 1}, {"*", 0, "*", 0}, {"*", 0, 
   "*", "*"}, {"*", "*", 1, 1}, {"*", "*", 1, 0}, {"*", "*", 1, 
   "*"}, {"*", "*", 0, 1}, {"*", "*", 0, 0}, {"*", "*", 0, "*"}, {"*",
    "*", "*", 1}, {"*", "*", "*", 0}};

h @ List1 and List2 are same up to sorting:

Sort @ h @ List1 == Sort @ List2

True

$\endgroup$
  • $\begingroup$ Works perfect, the bad thing I am do not understand what is what inside it yet :D $\endgroup$ – Evgeny Kuznetsov Aug 27 at 23:07
  • $\begingroup$ What I notice just now is that $h$ does not give all elements when length of list is greater then 4. In particular, when an initial list List1 is the list of all lists with exactly one $1$ inside, then the list of all "intersections" should be of size $\sum_n^kC_n^k-1$ and to have all desired elements I need to call the function $h$ twice. Can you change the code in such a way that it iterates itself until all "intersections" are there inside an output list? $\endgroup$ – Evgeny Kuznetsov Sep 4 at 15:32
  • $\begingroup$ Oh, thanks for edit!!! $\endgroup$ – Evgeny Kuznetsov Sep 4 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.