1

I'm looking for an algorithm to help me out with a combination of combinations problem.

I have generated two lists of combinations of letters: (26 choose 6) & (26 choose 5)

My goal is to be able to generate all sets of the alphabet in four groupings of 5 and one grouping of 6. For example:

{ [abcdef], [ghijk], [lmnop], [qrstu], [vwxyz] }

or

{ [vkjxqz], [etaoi], [nshrd], [lcumw], [fgypb] }

I wrote a simplistic nested algorithm to generate the combinations, but I now realize that the method I employed will generate a very large number of duplicate sets, which I wish to avoid. The algorithm I wrote will have to create approximately 2.7e+15 combos which is excessive to say the least.

For example, these two sets are functionally the same:

{ [abcdef], [ghijk], [lmnop], [qrstu], [vwxyz] }
{ [fabcde], [lmnop], [ghijk], [vwxyz], [qrstu] }

So I'm wondering how to write an algorithm to separate the alphabet into 5 "chunks" without generating any duplicate/overlapping sets.

The rules I want to adhere to are fairly simple:

1) The order of the letters in a set does not matter: [abcdef] == [ebdfac]

2) The order of each individual set within the outer set does not matter:

{ [abcdef], [ghijk], [lmnop], [qrstu], [vwxyz] } 
== 
{ [abcdef], [lmnop], [ghijk], [qrstu], [vwxyz] }

3) The set as a whole will contain all letters of the alphabet, without duplication.

Can anyone point me in the right direction?

If possible, I would like to be able to vary this to use different set sizes (e.g. 2 groups of 6 and 2 groups of 7 etc.), but if I can get the groupings illustrated only, that would more than enough.

  • python itertools does all this out of the box. – Steven Burnap Apr 21 '16 at 21:25
  • 1
    What do you need this for? It's very likely better to state and then try to solve your original problem. – gnasher729 Apr 22 '16 at 8:27
  • @gnasher729 I'm trying to find an optimal set of groups of letters. I want to take each set and run it through a function to give it a score. I'm trying to find the set that has the 'best score', but I want to do the minimum iterations possible. – hobwell Apr 23 '16 at 5:54
  • Do you really need them all? Your calculation is only off by a factor of 24, there will still be 1.1x10^14 partitions meeting your specifications. – kevin cline Apr 23 '16 at 19:03
  • 1
    There are four sets of five. There are 24 ways to order them. You counted every ordering of the same four sets, so that you counted both [abcde], [fghij], [klmno], [pqrst] and [fghij], [abcde], [klmno], [pqrst]. Since the sets are not ordered, I just divided your number by 24. – kevin cline Apr 25 '16 at 18:21
1

First, I'd start with a combinations generator.

Mine (shown below) is an iterator that you initialize with the number of total items to choose from (up to 64, e.g. 26), and the combination size you want (e.g. 6). It is written in C# and uses bit positions in a ulong to indicate selections.

On to the larger algorithm:

I'd generate the combinations for the first group of 6. With this set of combinations, "a" will be represented by bit position 0, and "z" by bit position 25.

For each combination of size 6 above, I'd now generate combinations for a dynamic abstract set, where this set has only 20 elements corresponding to the remaining 20 (given the 6 already selected for each combo of 6). We'll use the same combo generator for that, but when we get the results, we'll have to map them into the alphabet dynamically. So a bit position 0 in this dynamic combination will correspond to letter associated with the the first zero bit in the above size 6 combination; bit position 1 will correspond to the second zero bit in the above size 6 combination, and so forth.

Then I'd generate combinations for another dynamic abstract set, where this set has only 15 elements (and then 10). For this round, we again use the same combinations generator, and map the returned bits to the remaining unselected (0 bits) after both the size 6 combination and first size 5 combination are taken into account.

The last 5 letters don't need to be generated, as they are simply the remaining 5 unselected items.

So, there's two parts of significance: a simple combinations generation algorithm, and the notion of dynamically mapping the results of a nested combination onto the remaining letters of the enclosing combinations.

Below I show how the first dynamic nested combination would map to the parent combination.


foreach ( var i6Combo in new CombinationsGenerator ( 26, 6 ) )
{
    System.Console.WriteLine ( "i6 combo = " + Convert.ToString ( (long) i6Combo, 2 ).PadLeft ( 26, '0' ) );

    var i5Map = new int [ 20 ];
    int mapIndex = 0;
    foreach ( var i6RemainingZeroBit in new BitEnumerator ( i6Combo, 26, 0 ) )
        i5Map [ mapIndex++ ] = i6RemainingZeroBit;

    foreach ( var i5Combo1 in new CombinationsGenerator ( 20, 5, 31<<5 ) ) {
        var i5MappedCombo1 = 0UL;
        foreach ( var oneBitPosition in new BitEnumerator ( i5Combo1, 20, 1 ) )
            i5MappedCombo1 |= 1UL << i5Map [ oneBitPosition ];

        System.Console.WriteLine ( "i51 nested combo = " + Convert.ToString ( (long) i5MappedCombo1, 2 ).PadLeft ( 26, '0' ) );
        //break;
    }
}

/*
 * Copyright 2016 Erik L. Eidt (C), All rights reserved.
 * I put these classes, CombinationsGenerator, and BitEnumerator 
 * into the public domain, see the license here:
 *  https://creativecommons.org/publicdomain/zero/1.0/legalcode
 * You are free to use them without charge, as long as you don't claim authorship (moral rights), and otherwise observe the license.
 */

struct CombinationsGenerator : IEnumerable<ulong>, IEnumerator<ulong>
{
    public readonly int OutOfSize; //       count of total elements to choose from
    private readonly ulong _first; //       the first combination we'll generate
    private readonly ulong _last; //        the last combination we'll generate
    private readonly ulong _stopBefore; //  quit at reaching this value
    private ulong _curr; //                 the current combination, valid after first MoveNext ()
    private int _lastOneBit; //             position of lowest order "1" bit

    public CombinationsGenerator ( int outOfSize, int comboSize, ulong stopBefore = 0 )
    {
        OutOfSize = outOfSize;
        _stopBefore = stopBefore;
        _lastOneBit = 0;
        _curr = 0;
        _first = (1UL << comboSize) - 1;
        _last = _first << (outOfSize - comboSize);
    }

    public bool MoveNext ()
    {
        if ( _curr == _last )
            return false;

        if ( _curr == 0 )
        {
            _curr = _first;
            return true;
        }

        var result = _curr;

        int nextZeroBit;
        for ( nextZeroBit = _lastOneBit + 1; nextZeroBit < OutOfSize; nextZeroBit++ )
        {
            if ( (result & (1UL << nextZeroBit)) == 0 )
                break;
        }

        int numberOfOnesInARowBeforeFirstZero = nextZeroBit - _lastOneBit;

        var onesMask = ((1UL << numberOfOnesInARowBeforeFirstZero) - 1) << _lastOneBit;
        result &= ~onesMask; // clear the series of one's

        result |= 1UL << nextZeroBit; // set the first zero bit after the ones in a row

        var lowOnesReplacement = (1UL << (numberOfOnesInARowBeforeFirstZero - 1)) - 1;
        result |= lowOnesReplacement; // set the lowest bits to make up for the cleared bits

        _lastOneBit = lowOnesReplacement != 0 ? 0 : nextZeroBit;

        _curr = result;

        return result != _stopBefore;
    }

    public ulong Current => _curr;

    object IEnumerator.Current => _curr;

    public void Reset () { }
    public void Dispose () { }

    public IEnumerator<ulong> GetEnumerator () => this;
    IEnumerator IEnumerable.GetEnumerator () => this;
}

struct BitEnumerator : IEnumerable<int>, IEnumerator<int>
{
    private readonly ulong _pattern;
    private readonly int _size;
    private readonly int _bitValue;
    private int _position;

    public BitEnumerator ( ulong pattern, int size, int bitValue )
    {
        _pattern = pattern;
        _size = size;
        _bitValue = bitValue;
        _position = -1;
    }

    public int Current => _position;
    object IEnumerator.Current => _position;

    public void Dispose () { }

    public bool MoveNext ()
    {
        if ( _bitValue == 0 )
            while ( _position < _size && (_pattern & (1UL << ++_position)) != 0 ) {}
        else
            while ( _position < _size && (_pattern & (1UL << ++_position)) == 0 ) {}

        return _position < _size;
    }

    public void Reset () { }

    public IEnumerator<int> GetEnumerator () => this;
    IEnumerator IEnumerable.GetEnumerator () => this;
}
  • This was the exact approach I tried initially, but with linq instead of bit masking. The problem is, as you approach the end of the set of sixes, you're generating repeat combination sets in the 4 sets of 5. That duplication is what I am trying to avoid. – hobwell Apr 22 '16 at 21:01
  • No, I don't think they are repeated; they are necessary. The first set of 5 generates from 20 elements. The 2nd set of five will generate from 15 elements, and the 3rd set of size 5 from 10 elements. The last set of 5 is simply given. They are each fundamentally different elaborations, when you take mapping into account. It is true that for each set of 6 similar sets of 5 are generated, but not if you take mapping into account. Besides this combo generator is rather efficient, you'd be better of regenerating them than storing them, for example, because of the memory expansion. – Erik Eidt Apr 22 '16 at 21:06
  • Ok, I'm trying to hear what you're saying, but I don't think this will generate any repeats in the overall match, unless I misunderstood the definition of duplicate. (Naturally there will be some repeats within sub-portions of the match, but you want those, because the whole match is different, right?) – Erik Eidt Apr 22 '16 at 21:24
  • Here is why I think there will be duplicates. Given the first three outer loops have generated the following values: [ a b c d e f ] [ g h i j k ] [ l m n o p ]. The 4th loop can now generate combos of 5 from the remaining 10 letters (qrstuvwxyz), each time the 5th loop will be made up of whatever letters are left. – hobwell Apr 23 '16 at 5:49
  • The first time 4th loop will generate [ q r s t u ] and the 5th will be [ v w x y z ]. The last time the 4th loop runs, it will generate [ v w x y z ] and the 5th loop will generate [ q r s t u ], which is a duplicate (since the first 3 loops haven't changed at all). The edges are not the only place this will happen, and it will happen for all levels of loops (except the first, which is made up of six). Does that make sense? – hobwell Apr 23 '16 at 5:49
-1

We will ignore the last group here.

Order within a group doesn't matter, so let's stick with alphabetical order. If you nest your loops the right way they will only generate letters that are in alphabetical order.

The order of the groups doesn't matter. So let's stick with groups that are in alphabetical order relative to each other. Again, if you nest your loops the right way they will only generate groups that are in alphabetical order.

Maybe I'll come back and write some code for it, but that's the key that you're looking for. If your code satisfies the above criteria then it will automatically avoid any duplicates from being generated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.