CODEWITHSUNDEEP
python
HighwayJohn
HighwayJohn

Reputation: 921

Finding the smallest common denominator

I have the following problem. I have a arrays of L binary entries.(L is usually between 2 and 8 if it is of interest.) All possible combinations do exist. So there are 2^L arrays in one realisation. Now each combination will get randomly a fitness value assigned. The fitness value is also either 1 or 0. Now for example it could be, that the following arrays have fitness value 0:

1000
1010
1100
1001
1011

Then it is true, that all arrays with a 10__ are zero and all with 1_00. This is actually my problem. I need an algorithm which find these similarities and sort them for their rank. Like 10__ is of rank 2 and 1_00 is of rank 3. It is most of the time possible to define all arrays with zero fitness either with a small number of low ranks or with many high ranks. So my output must be ordered and I need to know how many I have of each rank. I can imagine that this is a known problem and there is already a solution? I hope you can help :)

Upvotes: 2

Views: 351

Answers (2)

vmonteco
vmonteco

Reputation: 15393

Assuming that this fitness value may depend of the value of each bit in your binary entry, and that you're searching the rules that can sum up your truth table (I'm not sure I understood your question very well about this point), You could use something like a Karnaugh map

These maps work like this :

You list your factors (here value of 1st bit, 2nd bit...) and separate them in two lists (one for the rows, one for the columns).

Order each list with a Gray Code.

Use the set of values for each list for respectively columns and rows in a table.

You know have a table that represent every possibilities of values for your binary entries.

Then, you list the fitness values for each entry in your table (1 or 0).

Then you'll have to make groups of Trues values (or false) in your table and that will permit you to find the rule for this group (by finding the common caracteristics). You usually group these by squares, or by corners (cf. first wikipedia link).

Here is a (simple) example with 3 bit entries :

Assuming you have the following Truth table :

ABC|R
-----
000|0
001|0
010|1
011|1
100|1
101|0
110|1
111|1

You can establish the following Karnaugh table :

        AB
  |     00 |     01 |     11 |     10   <-- AB
--------------------------------------
0 |      0 | (1)  1 | (1)  1 | (2)  1
--------------------------------------
1 |      0 | (1)  1 | (1)  1 |      0

^
|
C

  • You can group the 4 in the middle, these 4 have all B True, but A and C may be True or False, so you can sum it up like this :

    (1) B -> R

  • You also have the one on the top right :

    (2) A and !B and !C -> R

So your rule in this case is :

B or (A and !B and !C) -> R

As I mentionned in my comment, I am not sure about what you really want to achieve. But if you're trying to find some simple rules to sum up your truth table, maybe listing the rules found with this step is enough?

I have no python implementation to provide but you may find some on the internet. :) At least you can do it with paper and pencil now. :)

Feel free to ask if something isn't clear!

Here is one of the many tutorials you can find on the internet :

http://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html

PS :

B means that B is true, and !B means it's false.

PS-2 :

You can also use Boole algebra to reduce your rules.

Upvotes: 1

EdC
EdC

Reputation: 61

As already mentioned, this is a combinational logic minimization problem.

The algorithm typically used is Quine-Mccluskey and somebody has already asked for and posted a Python implementation:

Quine-McCluskey algorithm in Python

Upvotes: 1

Related Questions