Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

How can I get an array of bool combinations in order from least trues to most trues?

Tags:

arrays

c#

boolean

combinations

unity3d

I am trying to create an array of bool arrays. I want to have every combination of bool arrays with the exception of {false, false, false, false}. I want the order of this array to hold its sub arrays such that it ascends in the order of least trues to most trues. (Backwards order is fine, but it must still be ordered.)

Each subset of arrays such that they have the same number of trues should be in random order.

I can hardcode it as such:

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>();
    fourDoorList.Add(new bool[4] { true, true, true, true });
    fourDoorList = fourDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var threeDoorList = new List<bool[]>();
    threeDoorList.Add(new bool[4] { true, true, true, false });
    threeDoorList.Add(new bool[4] { true, true, false, true });
    threeDoorList.Add(new bool[4] { true, false, true, true });
    threeDoorList.Add(new bool[4] { false, true, true, true });
    threeDoorList = threeDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var twoDoorList = new List<bool[]>();
    twoDoorList.Add(new bool[4] { true, true, false, false });
    twoDoorList.Add(new bool[4] { true, false, true, false });
    twoDoorList.Add(new bool[4] { true, false, false, true });
    twoDoorList.Add(new bool[4] { false, true, true, false });
    twoDoorList.Add(new bool[4] { false, true, false, true });
    twoDoorList.Add(new bool[4] { false, false, true, true });
    twoDoorList = twoDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var oneDoorList = new List<bool[]>();
    oneDoorList.Add(new bool[4] { true, false, false, false });
    oneDoorList.Add(new bool[4] { false, true, false, false });
    oneDoorList.Add(new bool[4] { false, false, true, false });
    oneDoorList.Add(new bool[4] { false, false, false, true });
    oneDoorList = oneDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorList);
    boolArrayList.AddRange(threeDoorList);
    boolArrayList.AddRange(twoDoorList);
    boolArrayList.AddRange(oneDoorList);
    return boolArrayList.ToArray();
}

But that is so very dirty!

I can create a list like such, but these are unordered in the way I want:

private bool[][] GetBoolArrays()
{
    const int subArraySize = 4;
    bool[][] combinations = new bool[(int)Mathf.Pow(2, subArraySize) - 1][];
    for (int i = 1; i < Mathf.Pow(2, subArraySize); i++)
    {
        string binary = System.Convert.ToString(i, 2);
        while (binary.Length < subArraySize)
        {
            binary = 0 + binary;
        }
        bool[] singleCombination = binary.Select(c => c == '1').ToArray();
        combinations[i - 1] = singleCombination;
    }
    return combinations;
}

So to clarify, I am trying to create an array of arrays. Each sub array has 4 bools. The main array has every combination of subarrays except for all false. The subarrays should be ordered by number of trues, but each section with a set number of trues should be randomized.

I apologize if this is a poor explanation of what I am after...it is a bit difficult to explain. I can clarify on anything needed. Any ideas on how I can clean up the hard coded version of this?

like image 209
Evorlor Avatar asked Dec 11 '22 17:12

Evorlor

1 Answers

Let's make a series of small refactorings. We start with:

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>();
    fourDoorList.Add(new bool[4] { true, true, true, true });
    fourDoorList = fourDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var threeDoorList = new List<bool[]>();
    threeDoorList.Add(new bool[4] { true, true, true, false });
    threeDoorList.Add(new bool[4] { true, true, false, true });
    threeDoorList.Add(new bool[4] { true, false, true, true });
    threeDoorList.Add(new bool[4] { false, true, true, true });
    threeDoorList = threeDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var twoDoorList = new List<bool[]>();
    twoDoorList.Add(new bool[4] { true, true, false, false });
    twoDoorList.Add(new bool[4] { true, false, true, false });
    twoDoorList.Add(new bool[4] { true, false, false, true });
    twoDoorList.Add(new bool[4] { false, true, true, false });
    twoDoorList.Add(new bool[4] { false, true, false, true });
    twoDoorList.Add(new bool[4] { false, false, true, true });
    twoDoorList = twoDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var oneDoorList = new List<bool[]>();
    oneDoorList.Add(new bool[4] { true, false, false, false });
    oneDoorList.Add(new bool[4] { false, true, false, false });
    oneDoorList.Add(new bool[4] { false, false, true, false });
    oneDoorList.Add(new bool[4] { false, false, false, true });
    oneDoorList = oneDoorList.OrderBy(c => Random.Range(float.MinValue, float.MaxValue)).ToList();
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorList);
    boolArrayList.AddRange(threeDoorList);
    boolArrayList.AddRange(twoDoorList);
    boolArrayList.AddRange(oneDoorList);
    return boolArrayList.ToArray();
}

First thing we notices is that the shuffle code is duplicated. Extract it to a helper extension. Also, why do we need to turn this into a list? We're just going to pass it to AddRange later. Keep it as a sequence.

static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items)
{
  return items.OrderBy(c => Random.Range(float.MinValue, float.MaxValue));
}

Also, we now have a shuffled sequence and an unshuffled list. Keep them separate variables.

Also, we notice that there is no point shuffling the list that has only one thing in it!

OK, now what have we got?

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>();
    fourDoorList.Add(new bool[4] { true, true, true, true });
    var fourDoorListShuffle = fourDoorList; // No point shuffling!
    var threeDoorList = new List<bool[]>();
    threeDoorList.Add(new bool[4] { true, true, true, false });
    threeDoorList.Add(new bool[4] { true, true, false, true });
    threeDoorList.Add(new bool[4] { true, false, true, true });
    threeDoorList.Add(new bool[4] { false, true, true, true });
    var threeDoorListShuffle = threeDoorList.Shuffle();
    var twoDoorList = new List<bool[]>();
    twoDoorList.Add(new bool[4] { true, true, false, false });
    twoDoorList.Add(new bool[4] { true, false, true, false });
    twoDoorList.Add(new bool[4] { true, false, false, true });
    twoDoorList.Add(new bool[4] { false, true, true, false });
    twoDoorList.Add(new bool[4] { false, true, false, true });
    twoDoorList.Add(new bool[4] { false, false, true, true });
    var twoDoorListShuffle = twoDoorList.Shuffle();
    var oneDoorList = new List<bool[]>();
    oneDoorList.Add(new bool[4] { true, false, false, false });
    oneDoorList.Add(new bool[4] { false, true, false, false });
    oneDoorList.Add(new bool[4] { false, false, true, false });
    oneDoorList.Add(new bool[4] { false, false, false, true });
    var oneDoorListShuffle = oneDoorList.Shuffle();
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorListShuffle);
    boolArrayList.AddRange(threeDoorListShuffle);
    boolArrayList.AddRange(twoDoorListShuffle);
    boolArrayList.AddRange(oneDoorListShuffle);
    return boolArrayList.ToArray();
}

What else do we notice? We say "new bool[4]" but the compiler can infer both the type and the number.

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>();
    fourDoorList.Add(new[] { true, true, true, true });
    var fourDoorListShuffle = fourDoorList; // No point shuffling!
    var threeDoorList = new List<bool[]>();
    threeDoorList.Add(new[] { true, true, true, false });
    threeDoorList.Add(new[] { true, true, false, true });
    threeDoorList.Add(new[] { true, false, true, true });
    threeDoorList.Add(new[] { false, true, true, true });
    var threeDoorListShuffle = threeDoorList.Shuffle();
    var twoDoorList = new List<bool[]>();
    twoDoorList.Add(new[] { true, true, false, false });
    twoDoorList.Add(new[] { true, false, true, false });
    twoDoorList.Add(new[] { true, false, false, true });
    twoDoorList.Add(new[] { false, true, true, false });
    twoDoorList.Add(new[] { false, true, false, true });
    twoDoorList.Add(new[] { false, false, true, true });
    var twoDoorListShuffle = twoDoorList.Shuffle();
    var oneDoorList = new List<bool[]>();
    oneDoorList.Add(new[] { true, false, false, false });
    oneDoorList.Add(new[] { false, true, false, false });
    oneDoorList.Add(new[] { false, false, true, false });
    oneDoorList.Add(new[] { false, false, false, true });
    var oneDoorListShuffle = oneDoorList.Shuffle();
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorListShuffle);
    boolArrayList.AddRange(threeDoorListShuffle);
    boolArrayList.AddRange(twoDoorListShuffle);
    boolArrayList.AddRange(oneDoorListShuffle);
    return boolArrayList.ToArray();
}

Nicer. What if we used a collection initializer instead of all those calls to Add?

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>() {
      new[] { true, true, true, true }};
    var fourDoorListShuffle = fourDoorList; // No point shuffling!
    var threeDoorList = new List<bool[]>() {
      new[] { true, true, true, false },
      new[] { true, true, false, true },
      new[] { true, false, true, true },
      new[] { false, true, true, true }};
    var threeDoorListShuffle = threeDoorList.Shuffle();
    var twoDoorList = new List<bool[]>() {
      new[] { true, true, false, false },
      new[] { true, false, true, false },
      new[] { true, false, false, true },
      new[] { false, true, true, false },
      new[] { false, true, false, true },
      new[] { false, false, true, true }};
    var twoDoorListShuffle = twoDoorList.Shuffle();
    var oneDoorList = new List<bool[]>() {
      new[] { true, false, false, false },
      new[] { false, true, false, false },
      new[] { false, false, true, false },
      new[] { false, false, false, true }};
    var oneDoorListShuffle = oneDoorList.Shuffle();
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorListShuffle);
    boolArrayList.AddRange(threeDoorListShuffle);
    boolArrayList.AddRange(twoDoorListShuffle);
    boolArrayList.AddRange(oneDoorListShuffle);
    return boolArrayList.ToArray();
}

Better. What do we need the explaining variables for?

private bool[][] GetBoolArrays()
{
    var fourDoorList = new List<bool[]>() {
      new[] { true, true, true, true }};
    var threeDoorList = new List<bool[]>() {
      new[] { true, true, true, false },
      new[] { true, true, false, true },
      new[] { true, false, true, true },
      new[] { false, true, true, true }};
    var twoDoorList = new List<bool[]>() {
      new[] { true, true, false, false },
      new[] { true, false, true, false },
      new[] { true, false, false, true },
      new[] { false, true, true, false },
      new[] { false, true, false, true },
      new[] { false, false, true, true }};
    var oneDoorList = new List<bool[]>() {
      new[] { true, false, false, false },
      new[] { false, true, false, false },
      new[] { false, false, true, false },
      new[] { false, false, false, true }};
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorList);
    boolArrayList.AddRange(threeDoorList.Shuffle());
    boolArrayList.AddRange(twoDoorList.Shuffle());
    boolArrayList.AddRange(oneDoorList.Shuffle());
    return boolArrayList.ToArray();
}

Hmm, why do any of these have to be lists?

private bool[][] GetBoolArrays()
{
    var fourDoorList = new[] {
      new[] { true, true, true, true }};
    var threeDoorList = new[] {
      new[] { true, true, true, false },
      new[] { true, true, false, true },
      new[] { true, false, true, true },
      new[] { false, true, true, true }};
    var twoDoorList = new[] {
      new[] { true, true, false, false },
      new[] { true, false, true, false },
      new[] { true, false, false, true },
      new[] { false, true, true, false },
      new[] { false, true, false, true },
      new[] { false, false, true, true }};
    var oneDoorList = new[] {
      new[] { true, false, false, false },
      new[] { false, true, false, false },
      new[] { false, false, true, false },
      new[] { false, false, false, true }};
    var boolArrayList = new List<bool[]>();
    boolArrayList.AddRange(fourDoorList);
    boolArrayList.AddRange(threeDoorList.Shuffle());
    boolArrayList.AddRange(twoDoorList.Shuffle());
    boolArrayList.AddRange(oneDoorList.Shuffle());
    return boolArrayList.ToArray();
}

A sequence of add-ranges is the same as a sequence of concats:

private bool[][] GetBoolArrays()
{
    var fourDoorList = new[] {
      new[] { true, true, true, true }};
    var threeDoorList = new[] {
      new[] { true, true, true, false },
      new[] { true, true, false, true },
      new[] { true, false, true, true },
      new[] { false, true, true, true }};
    var twoDoorList = new[] {
      new[] { true, true, false, false },
      new[] { true, false, true, false },
      new[] { true, false, false, true },
      new[] { false, true, true, false },
      new[] { false, true, false, true },
      new[] { false, false, true, true }};
    var oneDoorList = new[] {
      new[] { true, false, false, false },
      new[] { false, true, false, false },
      new[] { false, false, true, false },
      new[] { false, false, false, true }};
    return fourDoorList.
      Concat(threeDoorList.Shuffle()).
      Concat(twoDoorList.Shuffle()).
      Concat(oneDoorList.Shuffle()).
      ToArray();
}

That's a lot nicer looking than the original code. Notice how we simply made a series of clear, correct refactorings that made each revision a little bit better.

Now, can you make a method that takes the number of bools you want total, and the number you want true?

static IEnumerable<bool[]> Combinations(int totalCount, int trueCount) 
{ 
    You implement this
}

Suppose we had such a method, which is left as an exercise. (The combinatorics articles on my blog may help.)

Now we can write:

private bool[][] GetBoolArrays()
{
    var fourDoorList = Combinations(4, 4);
    var threeDoorList = Combinations(4, 3);
    var twoDoorList = Combinations(4, 2);
    var oneDoorList = Combinations(4, 1);
    return fourDoorList.
      Concat(threeDoorList.Shuffle()).
      Concat(twoDoorList.Shuffle()).
      Concat(oneDoorList.Shuffle()).
      ToArray();
}

Now, can you write a method that has this signature:

static IEnumerable<T> MultiConcat(IEnumerable<IEnumerable<T>> sequences) 
{
   ... you implement this ...
}

If you can, then you can write:

private bool[][] GetBoolArrays()
{
    var combinations = new[] {
      Combinations(4, 4).Shuffle(),
      Combinations(4, 3).Shuffle(),
      Combinations(4, 2).Shuffle(),
      Combinations(4, 1).Shuffle()};
    return combinations.MultiConcat().ToArray();
}

Which I think is really quite a bit easier to read than the original code. In fact, we could get it down to a single statement:

private bool[][] GetBoolArrays()
{
    return new[] 
    {
      Combinations(4, 4).Shuffle(),
      Combinations(4, 3).Shuffle(),
      Combinations(4, 2).Shuffle(),
      Combinations(4, 1).Shuffle()
    }.MultiConcat().ToArray();
}

But now we might be getting too concise.

But let's not stop now. There is a lot of duplicated code in there!

private bool[][] GetBoolArrays()
{
  var q = from num in new[] { 4, 3, 2, 1 }
          select Combinations(4, num).Shuffle();
  return q.MultiConcat().ToArray();
}

Oh wait, we already have a multi concat built into LINQ! Hey, sorry to make you do that exercise but I bet it built character.

private bool[][] GetBoolArrays()
{
  var q = from num in new[] { 4, 3, 2, 1 }
          select Combinations(4, num).Shuffle() into all
          from combinations in all
          from combination in combinations
          select combination;
  return q.ToArray();
}

And that's as concise as I'm going to make it.

Notice the lessons here:

  • Small changes iterated can lead to big results.
  • Extract operations to methods that specialize in those operations
  • Use compiler inference to reduce redundancy and increase readability
  • Code that uses expressions to describe values is usually more compact than code that use statements to describe operations.
  • Embrace abstraction. Notice how much easier everything got when we abandoned the desire to stuff everything into a list.
  • If you are going to realize things into lists or arrays, do so as late in the process as possible.
like image 123
Eric Lippert Avatar answered May 24 '23 19:05

Eric Lippert
Sign in to Comment

Related questions

Reactive extension Timer/Interval reset
Using Elvis operator in combination with string.Equals
Converter into euro c#
LINQ - List Lowest Prices Only
How to change view in WPF?
Sort 2d array rows in ascending order of their first elements in c#
Argument type is not assignable to parameter type and it should be
Is it possible to determine which instance of a class the current instance of a class is instantiated from?
How to clear the contents of a canvas in wpf?
CheckBox lists in ASP.NET MVC and bind it back to controller
Why is the logical call context not propagated across threads?
MongoDB C# Driver: API vs Linq Performance
What way is better: make own wrapper for DbContext or use DbContext in Controller
Handling tables in c# selenium
Cancel execution of command if it takes too long
DataGridView Preserve Selected Index and Scroll Position after update and reload
C# Single line if with void return
How to convert time in c#
OnSuspending event not triggered with UWP Windows 10
Is it more efficient to use hexadecimal instead of decimal?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!