How can degree of order in a list be measured?

Question

The following questions gave me food for thought:

• Efficient way to shuffle objects
• I'd like to write an "ultimate shuffle" algorithm to sort my mp3 collection

When you sort a list - you always have a base-line(numbers, alphabet, ...) which tell you how to order the list.

Question: When you shuffle a set - how would you measure "degree of order"?

For example: 9 8 7 6 5 4 3 2 1 is ordered, even if completely differently than 1 2 3 4 5 6 7 8 9. And 9 8 7 6 1 2 3 4 5 also has some order (if you look at it in chunks: 9 8 7 6 and 1 2 3 4 5). Another example could be 9 2 3 4 5 6 7 8 1. How can you determine if one listing is less or more ordered than another.

Note: since there has been some confusion about the goal of this question - I would like to specify, that I'm not looking for a method to measure randomness. 1234 is just a random set of 4 digits as 4213, but it seems to me that 1234 is more ordered than 4213. The comment about "Kolmogorov complexity" by user61852, or the answer by Mathew Foscarini which mentions measuring the deviation between neighboring numbers in a sequence, are the types of answers I am looking for. I'm not sure if the measure entropy approach in the comment by MichaelT helps identify order in a list - if the comments could be elaborated into answers that would be great.

Answer 1

The structure of an order set of numbers is measured by the deviation between the numbers.

Given a sequence of 1 2 3 4 5 6 7 8 each number deviates by 1 from it's neighbor. A consistent deviation applies the sequence has structure.

If two sequences share the same deviations between numbers, then they are of the same level of complexity or lack of complexity. 1 2 3 4 5 and 8 9 10 11 12 both deviate by 1 yet share no numbers.

Deviation doesn't apply what type of structure. It just defines a value for the structure. Example; 1 2 1 2 1 2 and 1 2 3 4 5 6 both have a deviation of 1.

A non-sequential and non-repeating deviation does not imply a random sequence. It just implies constant variation in the structure of the sequence.

Keep in mind that randomness and non-repeating are different. Random numbers do repeat, and they do run in sequence. The randomness of a sequence can only be a calculated by sampling other sequences from the same population of data. If you just have one sequence, then it's not possible to say if the whole sequence is random.

If we have a sequence of numbers that is 3 digits long, then randomly speaking every possible 3 digit number is possible. Roll a set of 3 dice enough times and the number 666 will up as many times as the number 123.

If you have a sequence of numbers. You could divide that sequence up into smaller pieces, and then calculate the odds of that small sequence appearing. If you find a sequence repeating more often then it should, then those pieces are not appearing randomly.

For example;

227322282364622617 broken into 2 digit numbers would be

22 73 22 28 23 64 62 26 17

The odds of a 2 digit number appear or 1 in 100, but the number 22 appears twice. If our sequence was long enough. We could tell if 22 is appearing more often than once for every 100 pairs.

Answer 2

When evaluating a shuffling algorithm to determine if it truly generates a "random" sequence you can't just look at once sequence. 1 2 3 4 5 is a perfectly valid result of shuffling 5 numbers. What's important when evaluating a shuffling algorithm is that every single possible ordering is equally likely. As such, every single possible ordering is a "valid" result of shuffling the list.

So, how do you determine if your shuffling algorithm is "fair" or if it's "biased"?

First you'll need to generate a lot of random sequences. It should be at least an order of magnitude, if not several, larger than the size of the list.

Next, determine what percentage of the time each item appears in each position of the list. You should find that each item appears in each position about 1/n% of the time (where n is the size of the list). If certain items are more likely to appear in certain positions, then your shuffling algorithm is not "fair".

Answer 3

Ordered means lack of deviance in progression, by repeating or incremental deviances. Like counting by ones, counting by two's, etc. However, arranging random numbers from smallest to largest is definately ordering them, unless it's hidden within a larger group of numbers.

An incremental deviance is also ordered, but not as much, such as 1,(+1) 2, (+2) 5.

2 4 6 8 is more ordered than 1 2 5 8 Even though the average deviance is smaller in the second number.

The key is the deviances of the deviances (of the deviances). So if you can measure that, determining whether there's a progression, or a pattern that repeats (or progresses), you should be able to compare one set of numbers to any other to determine if one is more ordered than the other as a factorable test.