Iterate once and only once through all the possible configurations of an array

I am trying to create a program that will iterate through all the possible combinations for a given array once and only once, and use those combinations to color a grid of dots. I’ve simplified the problem to a one-row, two-column grid with only two colors.

I think I could be able to color the dots if I can programmatically create these four different configurations of an array…

int [] dots = { colors[1], colors[0] };
int [] dots = { colors[1], colors[1] };
int [] dots = { colors[0], colors[0] };
int [] dots = { colors[0], colors[1] };

…assuming I have another array that is:

int [] colors = {#FFFFFF, #000000};

I’m relatively familiar with creating arrays, I know they can be modified, and I’m thinking I should use an if, else statement to check if a particular configuration of the array has already been drawn. But I have no idea how to do that check. Also possible this is a stupid way of trying to achieve my ultimate goal which is is 3x3 grid (with 512 possible combinations) similar to this. Anyone have any ideas? Thanks in advance for your help.

1 Like

Hi,

Your problem is a well known issue in programming :

3 Likes

Thanks @josephh, I appreciate the pointer. I read that article a few times but couldn’t quite wrap my head around what to do next. I’m a bit of a noob and probably in over my head. I’ve been able to get every dot to color with either white or black, but I can’t figure out how to (1) make sure I get all the possible combinations, and (2) make sure I get no duplicates. I gather I create a data[] array in which to produce all the possible combinations but I can’t figure out how to do that. If anyone has further advice I definitely welcome it. Here’s what I’ve got so far (with a 2 row, 2 column grid instead of one row):

 import processing.pdf.*;
 boolean savePDF = true;
 
 int colorset;
 color [] colorsetarray = {#FFFFFF, #000000}; 
 
 void setup () {
   size(400, 400);
   noLoop(); //prevents video playback
 }
 
 void draw () {
   beginRecord(PDF, "Arabesque"+year()+"-"+"0"+month()+"-"+day()+"_"+hour()+minute()+"0"+second()+".pdf" );
   
   for (int y=20; y<height; y += 50) {
     for (int x=20; x<width; x += 50) {
    drawGrid(x,y);
     }
   }
 
   // saves the image when you play the sketch with the date and seconds in the sketch folder
   endRecord();
 }
 
 void drawGrid (float x, float y) {
   noStroke();
   fill(colorsetarray[int(random(2))]);
   circle(x,y,6);
   fill(colorsetarray[int(random(2))]);
   circle(x+9,y,6);
   fill(colorsetarray[int(random(2))]);
   circle(x,y+9,6);
   fill(colorsetarray[int(random(2))]);
   circle(x+9,y+9,6);
   }

image

1 Like

start of with 2 empty ArrayLists (for flexibility). In the first one you will assign a new random variable and the add it to your first arraylist after checking if the ArrayList contains the new value or not.

Now if you know how many combinations to expect you know the maximum size the first ArrayList needs to be, so we need an if statement to increment a counter that tells us when we are trying to add a value that is already in the array, but we need to make sure we only count it once so we get an accurate idea of the number of combinations we have explored. Thats why I suggest using a second Arraylist. This one shall also only be populated after a second test to see if the second array contains your new value, then finally add a condition to your loop that compares your counter to how big the first or second ArrayList is, if its the size of the predetermined max for the combinations you’ve explored all combinations and the job is done.

1 Like

to work out total combinations you need to understand what operations you are going to do. Say you are picking from a set value which can be reused then you would calculate x^y, x will be the number of choices you can make and y being the number of times you are allowed to make a choice. The number of choices remains the same as all probabilities are still available each time you choose. ( Think putting a card back into the deck, throwing a dice or flipping a coin).
If the choices cannot be reused then you would use the factorial to find out your max combinations, ie;

pick a card from a set of cards and then do not put your choice back in the deck.

52 total cards so 52! max combinations if you decide that you have t make 52 choices.

If you are making less than 52 choices then you have to amend the factorial calculation. We know that to calculate factorial we have to do
totalChoices * (maximumChoices - currentChoice) currentChoice
being the number of times we have already chosen. And finally we multiply our last answer with any new choices, giving us.

totalChoices * maxChoicesAllowed((maximumChoices - currentChoice) currentChoice)

then you can combine your knowledge of everything discussed to calculate the maximum allowed combinations for you current problem.

1 Like

I made a working Sketch now.

I just put 9 nested for loops together to generate the bit pattern:


 for (int i0 = 0; i0 < 2; i0++) { 
    for (int i1 = 0; i1 < 2; i1++) { 
      for (int i2 = 0; i2 < 2; i2++) { 
         ....
            ......

Of course I wrote another Sketch to write these 9 lines with for-loops for me, so I don’t have to do it:



void setup() {

  size(800, 600);

  int numberOfDesiredForLoops = 9; 

  for (int i = 0; i < numberOfDesiredForLoops; i++) {
    println ( " for (int i"+i+" = 0; i"+i+" < 2; i"+i+"++) { " );
  }

  println ("");
  for (int i = 0; i < numberOfDesiredForLoops; i++) {
    print ( "i"+i+",");
  }
  println ("");
  println ("");

  for (int i = 0; i < numberOfDesiredForLoops; i++) {
    println ( "}");
  }
  println ("");

  exit();
} // func 
//

Chrisir

3 Likes

@paulgoux and @Chrisir this is great stuff! I’m chewing through it. Hilarious to make a program that will make the for loops. :laughing:

I’ve got the first part of @paulgoux’s suggestion working:

I’m not going to be the most efficient, but I think I’m on my way. I may report back if I have more questions, but thanks a ton for the really helpful guidance!

I like that! :wink:

I my Sketch (that I didn’t post, didn’t want to spoil the fun for you) it just produces the 512 permutations without random. That’s what the 9 nested for loops do. There is also a check for duplicates.

Chrisir

In my Sketch (that I didn’t post, didn’t want to spoil the fun for you) it just produces the 512 permutations without random.

:+1: And thanks for explaining what the for loops do. I’ve got some ideas for how to proceed, and this is a fun challenge, so I’ll keep following the path I’m on. If I lose my path though I might cry for help. :scream:

1 Like

Here is an arraylist constructor.

ArrayList<someClass> varName = new ArrayList<someClass>();

To add to the arraylist;

varName.add(someInstanceOfClass);

Read value

VarName.get(int);

Set value

varName.set(int, someInstanceOfClass);

Hello,

Please format your code for readability and so we can copy it easily:
https://discourse.processing.org/faq#format-your-code

Try to cut and paste your code into Processing and you will understand.

When I hover over this code I can use the copy icon that pops up in upper right.

Example:

void setup() 
	{
  size(700, 150);
  background(0);
  fill(0, 255, 0);
  textAlign(CENTER, CENTER);
  textSize(48);
  text("Please format your code. :)", width/2, height/2-10);
	}

:)

Thanks for the tip. I thought I had formatted it right, but apparently not, so I edited it to make it better (but it includes arrays instead of ArrayLists). I’m watching Shiffman videos to figure out ArrayLists, classes, etc.

This may not answer your questions but will give you something to think about. :slight_smile:

You already have all the possible combinations… you just have to think in binary (and hexadecimal) and extract the bits.

Then wield these bits as you desire to unleash your creative vision.

  for(int i=0; i<64; i++)
    {
    println(binary(i));
    }

Partial code to get you started:

void setup() 
  {
  size(100, 160);
  colorMode(RGB, 1); // Just using black 0 and white 1
  
  for(int i=0; i<16; i++)
    {
    println(binary(i));
    }
  
  for(int i=0; i<16; i++)
    {
    int a, b;
    
    a = i & 0x01;
    b = (a > 0) ? 1 : 0;
    print(b);
    fill(b);
    circle(20, i*10+5, 10);
    
    a = i & 0x02;
    b = (a > 0) ? 1 : 0;
    print(b);
    fill(b);
    circle(30, i*10+5, 10);
    
    a = i & 0x04;
    b = (a > 0) ? 1 : 0;
    print(b);
    fill(b);
    circle(40, i*10+5, 10);
    
    a = i & 0x08;
    b = (a > 0) ? 1 : 0;
    println(b);
    fill(b);
    circle(50, i*10+5, 10);
    }       
  }

References:

image

:)

3 Likes

@glv this is fantastic; THANK YOU! :raised_hands:

It’s gonna take me a bit to understand exactly what’s going on, but I think I’m getting the gist. Thanks also for pointing me to the reference. I love the way Processing lays out its documentation; so easy to read and understand (at least eventually if not at first).

1 Like

More for you…

One of the best tools in a programmers tool chest is knowing the resources available to you and learning to navigate and use them.

This is a very short list:

Resources < Click here to expand !

I encourage you to review the resources available here:

:)

1 Like

:+1: I love Coding Train. Have watched many of those videos (at least the Processing-specific ones) several times.

1 Like

all the possible configurations of an array

If by this you mean all the permutations, then check out Heap’s algorithm – and a recent implementation posted to the forum, here:

Hello,

I wonder if this is the same.

  • permutations would be 123, 132, 231, 213…

  • configurations in the sense above: 000, 001, 101, 111, …

You may be right. Because the question said “I’ve simplified the problem” it wasn’t clear to me what the ultimate goal was. There are two values in the simplified case, but it may scale up to permutation with repetition…?

https://rosettacode.org/wiki/Permutations_with_repetitions#Java

Ah, no, I see, I missed the goal link. That is combinations, not permutations. In fact, it is counting – base 2, but if there were 3 colors, it would be base 3…

1 Like