Return to Answer

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(girls[index], boys[partner[index]])

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have fast random access. After that you can append the shuffled chunk into one file for them all.

Here's an artical on this technique that comes with a rather nice visualization:

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(
    girls[index],  
    boys[partner[index]]
)

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have fast random access. After that you can append the shuffled chunk into one file for them all.

Here's an artical on this technique that comes with a rather nice visualization:

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(girls[index], boys[partner[index]])

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have true random access. After that you can append the shuffled chunk into one file for them all.

Here's a paper on this technique that comes with a rather nice visualization:

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(girls[index], boys[partner[index]])

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have fast random access. After that you can append the shuffled chunk into one file for them all.

Here's an artical on this technique that comes with a rather nice visualization:

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(girls[index], boys[partner[index]])

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole array. Then load up each memory sized chunk and shuffle it now that you have true random access. At this point you can blast everything into one shuffled file.

Here's a paper on this technique that comes with a rather nice visualization:

If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.

If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.

Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.

Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.

let partner = [0,1,2,3,4,5,6,7,8,9]

partner.shuffle()

Your 'function' is now partner[index]. You could use it like this:

dance(girls[index], boys[partner[index]])

Also, understand that in many languages, and data structures, if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.

If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.

So be sure you can't directly sort your array before you add a level of indirection you might not need.

As for the issue of large, if you're up against more references than will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better as a stream.

A two pass shuffle can read the array sequentially (as a stream) and work on a chunk small enough to fit in memory as a full blown random access array. Create files for each chunk. Append to the chunks randomly from the whole stream. Then, one at a time, load up each memory sized chunk and shuffle it now that you have true random access. After that you can append the shuffled chunk into one file for them all.

Here's a paper on this technique that comes with a rather nice visualization: