<p><strong>First of all</strong> - a number must not occur twice, that is implied since we're talking about permutations. So filling the table with a simple random(255) function won't work.</p>

<p><strong>Secondly</strong>, you need to ensure that there are no premature recurrence patterns:</p>

<p>Consider the values 1,2,3,4 - the permutation table 4,3,2,1 is not a very good one because of its short cyclic properties, i.e. 1 -> 4, 4 -> 1. Likewise with 4,2,3,1 or 1,2,3,4. The optimal tables take you all the way through all positions: 3,1,4,2 or 2,4,1,3.</p>

<p>This property becomes increasingly  important as you increase the number of dimensions and perform recursive lookups.</p>

<p>However this approach alone may create clusters of too similar values, which may or may not be wanted, which leads me to next point.</p>

<p><strong>Thirdly</strong>, When you generate a table with the non cyclic properties, you need to step through remaining unassigned indices in a random manner. When possible constrain the random step distance here to a certain min and max range, e.g. 5..120 to avoid clustered groups of similar values. These numbers are worth experimenting with. </p>

CC BY-SA 3.0
2016-01-25T11:29:40.773Z
Welcome to Computer Graphics SE! Re your second point, I looked at the cyclic decomposition of the permutation table used by Perlin. It consists of multiple cycles of lengths `{4, 121, 89, 12, 4, 15, 4, 6}`, so apparently that's good enough? (Or maybe it isn't and a different permutation table would be even "better"? Although I'm not sure a human could perceive the difference. Or is actually better to have multiple cycles?)  I'm not following your third point. A uniform random distribution of what? And what step distance do you mean?
Martin Ender
CC BY-SA 3.0
2016-01-25T11:53:09.523Z
Thanks! Yeah, that was quite cryptic I guess. It was years ago I experimented with this, so I don't recall the exact implementation, but when you have the implementation for the optimal path generation, it should become evident that you pick random positions of what is left of unused indices - it is that random step length I refer to. I updated the answer
mhbuur
CC BY-SA 3.0
2016-01-25T11:25:51.673Z
2016-01-25T11:51:00.367Z
2016-01-25T11:51:00.367Z
mhbuur
<p>One possibility might be to borrow from the cryptographic community and, in particular, the 8-bit to 8-bit substitution used in the AES/Rijndael cipher. 
The table and code to generate it <a href="https://en.wikipedia.org/wiki/Rijndael_S-box" rel="nofollow">can be found on wikipedia.</a></p>

<p>I'd guess that, in order to generate up to 256 additional tables, you could just do something like:</p>

<pre><code>Func(U8 input, U8 TableNum) = SBox( (TableNum + Sbox(input)) Mod256 )
</code></pre>

<p>(since the SBox function is quite non-linear)</p>

<p>Having said that, (and please forgive me if I've got some of the details wrong) in a past life I implemented Perlin noise using a relatively simple RNG/Hash function but found the correlation in X/Y/Z due to my simple mapping of 2 or 3 dimensions to a scalar value was problematic.  I found that a very simple fix was just to use a CRC, eg. <em>something like</em></p>

<pre><code>InputToRNGHash = CRC(Z xor CRC( Y xor CRC(X))). 
</code></pre>

<p>Given CRCs intrinsics may be built in to CPU HW, this can be fast approach.</p>

CC BY-SA 3.0
2016-01-25T13:09:10.607Z
2016-01-25T14:06:52.043Z
2016-01-25T14:06:52.043Z
Simon F
<p>I'm implementing <a href="http://mrl.nyu.edu/~perlin/noise/" rel="noreferrer">improved Perlin noise</a>. Its key feature for randomisation is the hardcoded permutation table, which gives essentially random but reproducible gradients at the cells of the grid. The permutation table is just a permutation of the integers <code>0..255</code>, and is usually the following table (copied straight from Perlin's original implementation):</p>

<pre><code>{151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7,
225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247,
120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33,
88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134,
139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220,
105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80,
73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86,
164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38,
147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101,
155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232,
178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12,
191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181,
199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236,
205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180};
</code></pre>

<p>For reference, a small patch drawn from the noise generated by this table looks like this:</p>

<p><a href="https://i.sstatic.net/Gyuqs.png" rel="noreferrer"><img src="https://i.sstatic.net/Gyuqs.png" alt="enter image description here"></a></p>

<p>However, I would like the code to be a bit more flexible and allow this table to be reshuffled so that I can create a completely new noise field (instead of just sampling it at a different offset). But not all permutations are equally well shuffled. In the unlikely event that the random permutation is just the sorted array from <code>0</code> to <code>255</code>, the noise would look like this instead:</p>

<p><a href="https://i.sstatic.net/3uC8M.png" rel="noreferrer"><img src="https://i.sstatic.net/3uC8M.png" alt="enter image description here"></a></p>

<p>That's kinda bad. Of course, at a chance of $1$ in $256!$, this is not a case I need to be worried about. But surely, this is not the only permutation that yields very noticeable artefacts. Reverse sorted and almost sorted permutations would likely have the same problems. So how many other permutations are unsuitable? Say the code would be used in a popular game to generate a random world up front, it would still be annoying if every 100,000th generated world would look remotely regular.</p>

<p>So the question is, what exactly makes a good (or a bad) permutation table, and how do I assess the quality of a permutation table programmatically, such that I can reshuffle the table once more in the unlikely event that I roll a "bad" table?</p>

CC BY-SA 4.0
2024-11-05T20:56:54.710Z
I had similar experience when generating a random permutation. I had a look, and if I did not like the result, I re-shuffled. However that's no longer random then: If you have additional requirements (like not too many sequential numbers), it's actually not as "random" as it seems.
U. Windl
<noise><mathematics><procedural-generation>
What makes a good permutation table?
Martin Ender
# What makes a good permutation table?

(Asked by: username_0 on 2016-01-25)

I'm implementing [improved Perlin noise](http://mrl.nyu.edu/~perlin/noise/). Its key feature for randomisation is the hardcoded permutation table, which gives essentially random but reproducible gradients at the cells of the grid. The permutation table is just a permutation of the integers `0..255`, and is usually the following table (copied straight from Perlin's original implementation):

```
{151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7,
225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247,
120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33,
88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134,
139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220,
105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80,
73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86,
164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38,
147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101,
155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232,
178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12,
191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181,
199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236,
205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180};

```

For reference, a small patch drawn from the noise generated by this table looks like this:

[![enter image description here](https://i.sstatic.net/Gyuqs.png)](https://i.sstatic.net/Gyuqs.png)

However, I would like the code to be a bit more flexible and allow this table to be reshuffled so that I can create a completely new noise field (instead of just sampling it at a different offset). But not all permutations are equally well shuffled. In the unlikely event that the random permutation is just the sorted array from `0` to `255`, the noise would look like this instead:

[![enter image description here](https://i.sstatic.net/3uC8M.png)](https://i.sstatic.net/3uC8M.png)

That's kinda bad. Of course, at a chance of $1$ in $256!$, this is not a case I need to be worried about. But surely, this is not the only permutation that yields very noticeable artefacts. Reverse sorted and almost sorted permutations would likely have the same problems. So how many other permutations are unsuitable? Say the code would be used in a popular game to generate a random world up front, it would still be annoying if every 100,000th generated world would look remotely regular.

So the question is, what exactly makes a good (or a bad) permutation table, and how do I assess the quality of a permutation table programmatically, such that I can reshuffle the table once more in the unlikely event that I roll a "bad" table?

**Tags:** noise, mathematics, procedural-generation

> **Comments:**
> **username_1**: I had similar experience when generating a random permutation. I had a look, and if I did not like the result, I re-shuffled. However that's no longer random then: If you have additional requirements (like not too many sequential numbers), it's actually not as "random" as it seems.  

---

## 2 answers

### Answer by username_2 on 2016-01-25. Score: 5

**First of all** - a number must not occur twice, that is implied since we're talking about permutations. So filling the table with a simple random(255) function won't work.

**Secondly**, you need to ensure that there are no premature recurrence patterns:

Consider the values 1,2,3,4 - the permutation table 4,3,2,1 is not a very good one because of its short cyclic properties, i.e. 1 -> 4, 4 -> 1. Likewise with 4,2,3,1 or 1,2,3,4. The optimal tables take you all the way through all positions: 3,1,4,2 or 2,4,1,3.

This property becomes increasingly important as you increase the number of dimensions and perform recursive lookups.

However this approach alone may create clusters of too similar values, which may or may not be wanted, which leads me to next point.

**Thirdly**, When you generate a table with the non cyclic properties, you need to step through remaining unassigned indices in a random manner. When possible constrain the random step distance here to a certain min and max range, e.g. 5..120 to avoid clustered groups of similar values. These numbers are worth experimenting with.

> **Comments:**
> **username_0**: Welcome to Computer Graphics SE! Re your second point, I looked at the cyclic decomposition of the permutation table used by Perlin. It consists of multiple cycles of lengths `{4, 121, 89, 12, 4, 15, 4, 6}`, so apparently that's good enough? (Or maybe it isn't and a different permutation table would be even "better"? Although I'm not sure a human could perceive the difference. Or is actually better to have multiple cycles?)  I'm not following your third point. A uniform random distribution of what? And what step distance do you mean?  
> **username_2**: Thanks! Yeah, that was quite cryptic I guess. It was years ago I experimented with this, so I don't recall the exact implementation, but when you have the implementation for the optimal path generation, it should become evident that you pick random positions of what is left of unused indices - it is that random step length I refer to. I updated the answer  

---

### Answer by username_3 on 2016-01-25. Score: 1

One possibility might be to borrow from the cryptographic community and, in particular, the 8-bit to 8-bit substitution used in the AES/Rijndael cipher.
The table and code to generate it [can be found on wikipedia.](https://en.wikipedia.org/wiki/Rijndael_S-box)

I'd guess that, in order to generate up to 256 additional tables, you could just do something like:

```
Func(U8 input, U8 TableNum) = SBox( (TableNum + Sbox(input)) Mod256 )

```

(since the SBox function is quite non-linear)

Having said that, (and please forgive me if I've got some of the details wrong) in a past life I implemented Perlin noise using a relatively simple RNG/Hash function but found the correlation in X/Y/Z due to my simple mapping of 2 or 3 dimensions to a scalar value was problematic. I found that a very simple fix was just to use a CRC, eg. *something like*

```
InputToRNGHash = CRC(Z xor CRC( Y xor CRC(X))). 

```

Given CRCs intrinsics may be built in to CPU HW, this can be fast approach.


---

