Algorithm to Generate All Possible Black and White Pixel Images in 640 x 360 Dimensions?

algorithm, image, matrix, permutation

Solution

First to answer your questions. Yes there will be writings on "some" pictures. Actually ever text written by human which fits in 640x360 pixels will show up. Also every other text (text not yet written or text that never will be written). Also you will see pictures of every human which is, was or will be alive. See Infinite Monkey Theorem for further information.

The code to create your wanted gif is fairly easy. I used Java for this. Note that you need an extra class: AnimatedGifEncoder. The Code is not memory-bound because the `AanimatedGifEncoder` will write each image to disk as soon it is computed. But make sure that you have enough disk space available.

import java.awt.Color;
import java.awt.image.BufferedImage;

public class BigPicture {
    private final int width;
    private final int height;

    private final int WHITE = Color.WHITE.getRGB();
    private final int BLACK = Color.BLACK.getRGB();

    public BigPicture(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public void process(String outFile) {
        AnimatedGifEncoder gif = new AnimatedGifEncoder();
        gif.setSize(width, height);
        gif.setTransparent(null); // no transparency
        gif.setRepeat(-1); // play only once
        gif.setDelay(0); // 0 ms delay between images,
                         // 'cause ain't nobody got time for that!
        gif.start(outFile);
        BufferedImage bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_BINARY);

        // set the image to all white
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                bufferedImage.setRGB(x, y, WHITE);
            }
        }

        // add white image
        gif.addFrame(bufferedImage);

        // add all other combinations
        while (increase(bufferedImage)) {
            gif.addFrame(bufferedImage);
        }

        gif.finish();
    }

    /**
     * @param bufferedImage
     *            the image to increase
     * @return false if last pixel set to black => image is complete black
     */
    private boolean increase(BufferedImage bufferedImage) {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (bufferedImage.getRGB(x, y) == WHITE) {
                    bufferedImage.setRGB(x, y, BLACK);
                    return true;
                }
                bufferedImage.setRGB(x, y, WHITE);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        new BigPicture(640, 360).process("C:\\temp\\bigpicture.gif");
        System.out.println("finished.");
    }
}

Please be aware that this will take some time. So don't bother waiting and enjoy your life instead! ;)

EDIT: Since my solution is a bit unclear i will explain the algorithm.

- I have defined a method called `increase`. This method takes the BufferedImage and changes the bit pattern of the image so that the next bit pattern appears. The method is just a bit addition. The method will return `false` if the image encounters the last bit pattern (all pixels are set to black).

- As long as it is possible to increase the bit pattern (i.e. `increase()` returns true) we will save the image as new frame and increase the image again.

- How the `increase()` method works: The method runs over the image first in x-direction then in y-direction. I assume that white pixels are `0` and black pixels are `1`. So, we want to take the bit pattern of the image and add `1`. We inspect the first pixel: if it is white (`0`) we can add `1` without an overflow so we turn the pixel to black (`0 + 1 = 1` => black pixel). After that we return from the method because we want to increase only one position. It returns `true` because an increase was possible. If we encounter a black pixel we have an overflow (`1 + 1 = 2` or in binary `10`). So we have to set the current pixel to white and add the `1` to the next pixel. This will continue until we find the first white pixel.

example: first we create a print method: this method prints the image as binary number. Attention the number is reversed and the most significant bit is the bit on the right side.

public void print(BufferedImage bufferedImage) {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (bufferedImage.getRGB(x, y) == WHITE) {
                System.out.print(0); // white pixel
            } else {
                System.out.print(1); // black pixel
            }
        }
    }
    System.out.println();
}

now we modify our main-while loop:

print(bufferedImage); // this one prints the empty image
while (increase(bufferedImage)) {
    print(bufferedImage);
}

and now set some short example to test:

new BigPicture(1, 5).process("C:\\temp\\bigpicture.gif");

and finally the output:

00000 // 0 this is the first print before the loop -> "white image"
10000 // 1 the first white pixel is set to black
01000 // 2 the first overflow, so the second pixel is set to black "2"
11000 // 3
00100 // 4
10100 // 5
01100
11100
00010 // 8
10010
01010
11010
00110
10110
01110
11110
00001 // 16
10001
01001
11001
00101
10101
01101
11101
00011
10011
01011
11011
00111
10111
01111
11111 // 31 == 2^5 - 1
finished.

Problem

Original source