Shuffled Combination of multiple List

Question

Similar question to this: Combination of List<List<int>>

However, the shuffling makes this non-trivial and IMO requires a much different solution. I'm happy to be proved wrong, but it's not as easy as shuffling the results since the resulting list can't fit into memory:

I have 3 LARGE lists I need to combine:

List<int> A = new List<int> {1, 2, 3, ...};
List<int> B = new List<int> {4, 5, 6, ...};
List<int> C = new List<int> {7, 8, 9, ...};

The output is a new List<object> { {1, 4, 7}, {1, 4, 8}, ... }

However, I the resulting list needs to be shuffled. Shuffling each individual list will not be sufficient if they are still patterned when combined, and while the 3 lists will fit in memory, the combination of all 3 will not. A shuffled index list is also apparently too large to store in memory.

I have tried a number of different approaches, but I cannot find a way to randomize the order without loading every item first. Is this possible? Thanks!

Answer 1

If all lists have the same size:

var aShuffle = new List<int>(A.Count);
aShuffle.AddRange(A.Shuffle());
var bShuffle = new List<int>(B.Count);
bShuffle.AddRange(B.Shuffle());
var cShuffle = new List<int>(C.Count);
cShuffle.AddRange(C.Shuffle());

List<Trio> trios = new List<Trio>(aShuffle.Count);
for (int i = 0; i < aShuffle.Count; i++)
{
    trios.Add(new Trio { Value1 = aShuffle[i], Value2 = bShuffle[i], Value3 = cShuffle[i] });
}

With this struct:

public struct Trio
{
    public int Value1 { get; set; }
    public int Value2 { get; set; }
    public int Value3 { get; set; }
}

I've used this extension to shuffle (Fisher-Yates) the collection:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
{
    return source.Shuffle(new Random());
}

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    if (source == null) throw new ArgumentNullException("source");
    if (rng == null) throw new ArgumentNullException("rng");

    return source.ShuffleIterator(rng);
}

private static IEnumerable<T> ShuffleIterator<T>(
    this IEnumerable<T> source, Random rng)
{
    List<T> buffer = source.ToList();
    for (int i = 0; i < buffer.Count; i++)
    {
        int j = rng.Next(i, buffer.Count);
        yield return buffer[j];

        buffer[j] = buffer[i];
    }
}

Demonstration

Value1: 3 Value2: 5 Value3: 8
Value1: 1 Value2: 6 Value3: 9
Value1: 6 Value2: 4 Value3: 7
Value1: 2 Value2: 8 Value3: 33

Answer 2

Have you tried to make use of the Union LINQ-Extension?

You can use it to unify your lists and then shuffle the result :)

Answer 3

To expand upon my comment...

Firstly, be sure that you can't do this shuffle in physical memory. If you have fewer than UInt32.MaxValue items you can still use managed arrays. Plus you only need to store an int (or possibly long) per item, not the item itself.

So, you have so many items you can't count them in memory?

Start off by storing a number for each item in a file.

using (var f = File.Create("shuffle.bin"))
{
    var length = A.Count * B.Count * C.Count;

    f.SetLength(length * sizeof(long));
    for (long i = 0; i < length; i++)
    {
        var bytes = BitConverter.GetBytes(i);
        f.Write(bytes, 0, sizeof(long));
    }
}

It would take forever to shuffle this file. So instead, we can shuffle one entry out at a time, on demand. This shouldn't take too long to extract one number.

using (var f = File.Open("shuffle.bin", FileMode.Open))
{
    // Calculate how many numbers are left in the file.
    long itemCount = f.Length / sizeof(long);
    if (itemCount == 0)
    {
        // We have used all the items - create another file, or throw
        // an exception, or whatever you want.
    }

    // You need an equivalent of `Random.Next(int max)` here that works on `long`s.
    long index = NextLong(itemCount);

    // Read out the number you've shuffled out.
    f.Seek(index * sizeof(long), SeekOrigin.Begin);
    var rtnBytes = new byte[sizeof(long)];
    f.Read(rtnBytes, 0, sizeof(long));

    // Read out the last number.
    f.Seek((itemCount - 1) * sizeof(long), SeekOrigin.Begin);
    var rplcBytes = new byte[sizeof(long)];
    f.Read(rplcBytes, 0, sizeof(long));

    // Replace the shuffled-out number with the last number.
    f.Seek(index * sizeof(long), SeekOrigin.Begin);
    f.Write(rplcBytes, 0, sizeof(long));

    // Trim the now-duplicate last number off the end of the file.
    f.SetLength((itemCount - 1) * sizeof(long));

    // Get the long and do with it what you want.
    long rtnLong = BitConverter.ToInt64(rtnBytes, 0);
}

You can then turn this long into a triple of indices as follows:

int indexA = (int)(rtnLong % (long)A.Count);
rtnLong /= a.Count;
int indexB = (int)(rtnLong % (long)B.Count);
rtnLong /= b.Count;
int indexC = (int)rtnLong;