Innanzitutto, inizierei con un generatore di combinazioni.
Il mio (mostrato sotto) è un iteratore che si inizializza con il numero di elementi totali tra cui scegliere (fino a 64, ad esempio 26) e la dimensione della combinazione desiderata (ad esempio 6). È scritto in C # e utilizza posizioni di bit in un ulong per indicare le selezioni.
Attivo all'algoritmo più grande:
Vorrei generare le combinazioni per il primo gruppo di 6. Con questo insieme di combinazioni, "a" sarà rappresentato dalla posizione del bit 0, e "z" dalla posizione del bit 25.
Per ogni combinazione della taglia 6 sopra, ora genererei combinazioni per un set astratto dinamico, dove questo set ha solo 20 elementi corrispondenti ai restanti 20 (dato il 6 già selezionato per ogni combinazione di 6). Utilizzeremo lo stesso generatore di combo per questo, ma quando avremo ottenuto i risultati, dovremo mapparli dinamicamente nell'alfabeto. Quindi una posizione di bit 0 in questa combinazione dinamica corrisponderà alla lettera associata al primo bit di zero nella combinazione di dimensione 6 di cui sopra; la posizione di bit 1 corrisponderà al secondo bit di zero nella combinazione di dimensioni 6 di cui sopra, e così via.
Quindi genererei combinazioni per un altro set astratto dinamico, dove questo set ha solo 15 elementi (e quindi 10). Per questo round, utilizziamo ancora lo stesso generatore di combinazioni e mappiamo i bit restituiti ai restanti non selezionati (0 bit) dopo aver preso in considerazione sia la combinazione di dimensioni 6 sia la prima combinazione di dimensione 5.
Non è necessario generare le ultime 5 lettere, poiché sono semplicemente i rimanenti 5 elementi non selezionati.
Quindi, ci sono due parti di significato: un algoritmo di generazione di combinazioni semplici e la nozione di mappare dinamicamente i risultati di una combinazione nidificata sulle lettere rimanenti delle combinazioni che racchiudono.
Qui sotto mostro come la prima combinazione nidificata dinamica si assocerebbe alla combinazione genitore.
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;
}