-1

I was having a discussion with a friend on the Infinite Monkey Theorem and that's when this came up. Suppose we want to generate an image of size 60 x 80 i.e. 4800 pixels and we want to use 8bpp (bits per pixel) or 1 byte for each colour (for a total of 256 colours).

Now what is the algorithm to generate all possible images using these values? I think the total number of images generated will be 256 ^ (60 x 80) i.e. 256 raised to the power 4800. Is there any algorithm that can be used to generate all combinations of colour values for 4800 pixel slots?

7
  • 3
    If you think of the entire image is one big 60 x 80 byte integer you can enumerate all the images by "counting". Start at 0 and count up until the max value.
    – MetaFight
    Sep 20, 2016 at 5:43
  • If you replace your starting example with size 2 x 2, notice that the problem you're asking to solve is equivalent to enumerating all 32-bit unsigned integers 0, 1, 2, ..., 4294967295. What do you plan on doing with all these generated images?
    – Brandin
    Sep 20, 2016 at 5:50
  • 3
    You are aware that 2^38400 is an absurdly large number, right? Sep 20, 2016 at 5:53
  • 2
    This is simply the positional number system in action. Instead of 10 digits you've got 256, but that's the entire difference. How do you enumerate all numbers? Enumerating all images works exactly the same way. Sep 20, 2016 at 5:53
  • For all those who are asking whether I know how big a task this is and how many values it is going to generate: Yes I know the amount of data this will generate. I just want to get the steps that I can use to generate it. What I'll will do with it or Why is not part of the question.
    – A9S6
    Sep 20, 2016 at 8:00

4 Answers 4

5

A 60 by 80 image where each pixel can have 256 colors (8 bits) expressed as a bitmap is simply an array of 60*80=4800 bytes.

If you treat the byte array as a single integer, simply count from 0 to 0xFFFF...FFFF (9,600 "F"s). Many modern languages have variable-length integer types (e.g. Java's BigInteger) that can handle numbers this big.

Each time you increment that super-large integer, you created a new image.

To display an image, simply chop that integer into 8 bit segments, and you have your 4,800 pixels. Each group of 60 pixels is a row. This is the basic idea behind bitmaps (.bmp files).

N.B. this program will run until the heat death of the universe.

2
  • Who could have imagined the universe would die by drowning in a virtually endless stream of images depicting binary integers, generated by some monkey algorithm?
    – COME FROM
    Sep 20, 2016 at 8:35
  • 1
    I assume you're using hexadecimal when you say to count to 0xFFFF...FFFF, in which case you should have (base 10) 9,600 "F"s. One hexadecimal digit is only 4 bits, not a full 8 bit byte.
    – 8bittree
    Sep 20, 2016 at 15:08
4

Here is how I would do it. Lets make it general and say image is width*height.

Pseudocode:

int[width*height] rawImage;

initialize all rawImage values to 0;

while (rawImage[width*height-1] < 256) {

    create255ImageFrom(rawImage);

    rawImage[0]++;
    for(int i = 0;i<width*height-1;i++)
    {
        if (rawImage[i] > 255){
            rawImage[i] = 0;
            rawImage[i+1]++;
        }
    }

}

There might be few off-by-one and edge errors. But it should generally work.

What it does is that it basically creates a "number" with width*height "digits" where each "digit" is 256 values. Then, when you increase the first digit and it goes over 255, it increases next "digit" by one and then sets itself to 0; And it goes like that until last digit is over 255, meaning it enumerated all values.

4
  • I am trying to run this for a 2x2 image with 2 colours, expecting 16 values but it does not seems to work as expected. "rawImage[0]" is incremented but never checked for > 255. Also not sure how the IF condition inside the FOR loop is going to be TRUE because we are incrementing [0] but checking >= [1] here.
    – A9S6
    Sep 20, 2016 at 7:07
  • 4
    if(Psudocode = not working code) then goto checkPrice
    – Ewan
    Sep 20, 2016 at 7:33
  • @A9S6 Yeah. Fixed that, hopefully.
    – Euphoric
    Sep 20, 2016 at 8:08
  • Personally I'd move the rawImage[i] > 255 check into the loop condition, but your way is correct as well. Sep 20, 2016 at 11:02
1

Nothing is as simple as it first seems...

If you generate all images, one image at a time, then it would be 256 ^ (60 x 80) images.

If you generate images in pairs, with a 60*160 pixel "2 images in one" image where one image is the top half and the other image is the bottom half; then it wouldn't change anything, and it'd still be 256 ^ (60 x 80) images total.

However, if you generate a 60*160 pixel "meta image" there's be one image starting on the top line, a second image starting on the second line, a third image on the third line, .... It would actually be a total of 80 images where each image overlaps the previous image by 79 rows of pixels. Some of those images wouldn't have been seen before, and don't need to be seen again, so it'd end up being less work.

What if you generated a 6000*8000 "meta image"? Each "meta image" would contain 10000 of the smaller 60 x 80 images that overlap each other. How much work would that save?

Now... What if you generate 1 image, and then rotate it 90 degrees? It's the same image. You can generate 1 image and that counts as 4 rotations * 2 mirrors = 8 variations of the same image.

The question then is: what is the smallest "meta image" you need to generate, such that the "meta image" contains all possible 60*80 images at least once, excluding rotations and mirrors? If you can answer that, then the amount of work will be significantly less than 256^(60*80).

For an example of what I'm saying; imagine it's 2 colours and 2*1 images. For this, the worst case (the maths everyone else is using) it'd be 2^(2*1) = 4 images, like this:

    00
    01
    10
    11

However, 01 and 10 are mirrors of each other, so you only need one. This gives the equivalent of 3 images:

    00
    01
    11

Now imagine a "meta image":

    0011

This contains all 3 of the previous images overlapping. However, this is a total of 4 pixels for all images, not a total of 8 pixels for all images. It's literally half as much work.

3
  • 2
    Do you have any idea how unimaginably huge 256 ^ (60 x 80) is? Minor optimizations won't make it any more feasible. Sep 20, 2016 at 7:52
  • 1
    It is not 1/2 the work. Flip a pair is no less work then just painting a pixel.
    – paparazzo
    Sep 20, 2016 at 11:21
  • @Paparazzi: Seriously? You have one image format where first row (in memory) is at bottom of the image and a different image format where first row (in memory) is at top of the image. How expensive do you think it is to flip the image while also converting from the first format to the second format?
    – Brendan
    Oct 19, 2016 at 4:08
0

for just a 2X2
brute force
answer from Euforic is better

UInt64 count = 0;
byte[,] image = new byte[2, 2];
for (int i = 0; i < 256; i++)
{
    image[0, 0] = (byte)i;
    for (int j = 0; j < 256; j++)
    {
        image[0, 1] = (byte)j;
        for (int k = 0; k < 256; k++)
        {
            image[1, 0] = (byte)k;
            for (int m = 0; m < 256; m++)
            {
                image[1, 1] = (byte)m;
                count++;
            }
        }
    }
}
System.Diagnostics.Debug.WriteLine(count.ToString());
System.Diagnostics.Debug.WriteLine(Math.Pow(256, 4).ToString());
1
  • 2
    Creating a separate loop for each pixel is pretty ugly. Sep 20, 2016 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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