array partition minimal difference

Question

I need to partition the array data according to minimal differences in C# / Java.

Input: { A1, A2, B3, D4, C7, B12, A12, C14, D15, C22, A23, B25, A35, A36, D37 }

e.g.

• Difference between B3, D4 = |3 - 4| = 1

• Difference between A23, B25 = |23 - 25| = 2

• Difference between D4, C7 = |4 - 7| = 3

• Difference between B12, A12 = |12 - 12| = 0

The rules are:

• For each group, letter cannot be repeated

• For each group, it can contains 1 - 4 elements

• Difference between element must be <= 3

---

Output: { A1 },{ A2, B3, D4, C7 },{ B12, A12, C14, D15 },{ C22, A23, B25 },{ A35 },{ A36, D37 }

Answer 1

This took only 10 minutes to code in the Dyalog APL parallel array processing language, but it took me 2 hours to write down the answer. I shall not submit any code at all, so to not break the language constraint in the question, but i will try to clarify the principle below, using data and some pseudocode.

Provided that the argument has fixed order, there are 512 possible solutions, as follows:

┌──────────┬─┬─┬──┬──┬───┬───┬──┬──┬──┬──┬─────┐
│Partitions│6│7│8 │9 │10 │11 │12│13│14│15│Total│
├──────────┼─┼─┼──┼──┼───┼───┼──┼──┼──┼──┼─────┤
│Solutions │1│9│36│84│126│126│84│36│9 │1 │512  │
└──────────┴─┴─┴──┴──┴───┴───┴──┴──┴──┴──┴─────┘

The solution with minimum partitions (6) is:

┌──┬───────────┬───────────────┬───────────┬───┬───────┐
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
└──┴───────────┴───────────────┴───────────┴───┴───────┘

The next ones (with 7 partitions) are:

┌──┬───────────┬───────────────┬───────────────┬───────────┬───┬───────┐
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25    │A35        │A36│D37    │
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23        │B25        │A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22            │A23 B25    │A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14    │D15            │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12        │C14 D15        │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12            │A12 C14 D15    │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4   │C7             │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3      │D4 C7          │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2         │B3 D4 C7       │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
└──┴───────────┴───────────────┴───────────────┴───────────┴───┴───────┘

The last one (into 15 partitions) is naturally:

┌──┬──┬──┬──┬──┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│A1│A2│B3│D4│C7│B12│A12│C14│D15│C22│A23│B25│A35│A36│D37│
└──┴──┴──┴──┴──┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

This best, most safe way to solve this problem is using brute force and walk through all possibilities. First you need to adapt the principle of using zeroes and ones to indicate partitioning locations. Since you have 15 elements in the argument, we use 15-length binary vectors to do the job. Example:

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition 'stackoverflowex'

implies / shall return 4 partitions:

┌───┬─────┬───┬────┐
│sta│ckove│rfl│owex│
└───┴─────┴───┴────┘

You can also partition another 15-length boolean vector:

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition (1 1 0 0 1 1 0 1 0 0 0 1 1 0 0)

shall return:

┌─────┬─────────┬─────┬───────┐
│1 1 0│0 1 1 0 1│0 0 0│1 1 0 0│
└─────┴─────────┴─────┴───────┘

and you can calculate the sum of ones in each partition. The one above would return:

┌─┬─┬─┬─┐
│2│3│0│2│
└─┴─┴─┴─┘

To solve your problem, you must generate all possible partition vectors. This is simpler done than said. You just need all partition vectors between these two:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // This would create 1 single, big partition
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 // This would create 15 small partitions

What are these? Very simple, they are 2-base (binary) representations of 16384 and 32767. You must simply loop through all numbers between 16384 and 32767 (both inclusive), convert each number to 2-base, partition your data by that, and see if the current partition is acceptable or not (= meets your criteria, like "For each group, letter cannot be repeated"). Converting all numbers in the interval will cover all possible partitions - any possible combination of zeroes and ones is in there. The calculation will take only a fragment of a second.

Pseudo:

// The character part of the argument: 15-length vector of characters:
Chars = "A","A","B","D","C","B","A","C","D","C","A","B","A","A","D" 

// From that, extract the locations of the unique characters:
CharsA = 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0 // Where Chars == A
CharsB = 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 // Where Chars == B
CharsC = 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 // Where Chars == C
CharsD = 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 // Where Chars == D

// The numeric part of the argument: 15-length vector of numbers:
// Btw, is this about lottery... hmmm
Nums = 1, 2, 3, 4, 7, 12, 12, 14, 15, 22, 23, 25, 35, 36, 37

:For Number :In [all numbers between 16384 and 32767]

    Base2 = [2-base of Number] // 20123 would give: 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1

    // Test 1: "For each group, it can contains 1 - 4 elements"
        [using Base2, partition the partition vector Base2 itself;
         bail out if any partition length exceeds 4]

    // Test 2: "Difference between element must be <= 3"
        [using Base2, partition Nums; 
         check differences inside each partition; 
         bail out if bigger than 3 anywhere]

    // Test 3: "For each group, letter cannot be repeated"
        [using Base2, partition CharsA, CharsB, CharsC, CharsD (each in turn);
         count number of ones in each partition;
         bail out if exceeds 1 anywhere (meaning a character occurs more than once)]

    // If we still are here, this partition Number is ACCEPTABLE
    [add Number to a list, or do a parallel boolean marking 1 for Number]

:End

At this point, 512 Number's fulfilled the conditions specified, while the rest failed in some of the tests. It is a pure coincidence, that they were 512, which is a special number for us coders. Assume you now have the 512 acceptable numbers in variable called Result. Now you need to sort it, by resolving number of partitions in each Result (= number of ones in it's binary representation). Do this by again converting each number in Result to base 2, then count & sum the number of ones in each, and sort ascending by that sum. The smallest sum will be 6, and it occurs once only - this is the partition mentioned at top of this answer.

It's value is 25126 and the 2-base for that is

1 1 0 0 0 1 0 0 0 1 0 0 1 1 0

Answer 2

The input you provided contains more than one solution. Probably around 15 or so (A1-A2, A35-A36, D4-C7 being the things that will change the solution). Since you didn't answer when I asked which solution you wanted, I wrote this code which will give ONE (the most simple) "solution" for this problem =)

static string[][] Solve(string[] input)
{
    List<string> myList = new List<string>(input);
    List<string[]> groups = new List<string[]>();
    while (myList.Count > 0)
    {
        string currentStr = myList[0];
        int currentNum = int.Parse(currentStr.Substring(1));
        List<string> lessThan4 = new List<string>();
        lessThan4.Add(currentStr);
        for (int i = 1; i < myList.Count; i++)
        {
            if (Math.Abs(currentNum - int.Parse(myList[i].Substring(1))) < 4)
            {
                // Add it to the list only if there's not the same letter in there
                if (!lessThan4.Where(a => a.Contains(myList[i].Substring(0, 1))).Any())
                {
                    lessThan4.Add(myList[i]);
                }
            }
        }

        lessThan4.Sort();
        groups.Add(lessThan4.ToArray());
        myList = myList.Except(lessThan4).ToList();
    }
    return groups.ToArray();
}

You can test it with something like:

string[] input = new string[] { "A2", "B3", "D4", "C7", "B12", "A12", "C14", "D15", "C22", "A23", "B25", "A35", "A36", "D37" };
Solve(input);

The output of Solve() in that case that will be:

{ A2, B3, D4 },{ C7 },{ B12, A12, C14, D15 },{ C22, A23, B25 },{ A35, D37 },{ A36 }

Important: this code assumes that the strings inside input are unique.