Algoritmo per creare tutti i set univoci dell'alfabeto utilizzando dimensioni di gruppo arbitrarie

1

Sto cercando un algoritmo per aiutarmi con una combinazione di combinazioni di problemi.

Ho generato due elenchi di combinazioni di lettere: (26 scegli 6) & (26 scegli 5)

Il mio obiettivo è essere in grado di generare tutti i set dell'alfabeto in quattro gruppi di 5 e un raggruppamento di 6. Ad esempio:

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

o

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

Ho scritto un algoritmo semplicistico annidato per generare le combinazioni, ma ora mi rendo conto che il metodo che ho impiegato genererà un numero molto grande di set duplicati, che desidero evitare. L'algoritmo che ho scritto dovrà creare circa 2.7e + 15 combo che è eccessivo a dir poco.

Ad esempio, questi due set sono funzionalmente identici:

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

Quindi mi chiedo come scrivere un algoritmo per separare l'alfabeto in 5 "blocchi" senza generare alcun set duplicato / sovrapposto.

Le regole a cui voglio aderire sono abbastanza semplici:

1) L'ordine delle lettere in un set non ha importanza:     [abcdef] == [ebdfac]

2) L'ordine di ogni singolo set all'interno del set esterno non ha importanza:

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

3) L'insieme nel suo insieme conterrà tutte le lettere dell'alfabeto, senza duplicazione.

Qualcuno può indicarmi la giusta direzione?

Se possibile, mi piacerebbe essere in grado di variare questo per utilizzare diverse dimensioni di set (ad esempio 2 gruppi di 6 e 2 gruppi di 7 ecc.), ma se riesco a ottenere solo i raggruppamenti illustrati, sarebbe più che sufficiente .

    
posta hobwell 21.04.2016 - 22:56
fonte

2 risposte

1

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;
}
    
risposta data 22.04.2016 - 20:53
fonte
-1

Qui ignoreremo l'ultimo gruppo.

L'ordine all'interno di un gruppo non ha importanza, quindi continuiamo con l'ordine alfabetico. Se annidate i vostri loop nel modo giusto, solo generano lettere che sono in ordine alfabetico.

L'ordine dei gruppi non ha importanza. Quindi rimaniamo con gruppi che sono in ordine alfabetico l'uno rispetto all'altro. Di nuovo, se annidate i vostri loop nel modo giusto, solo generano gruppi che sono in ordine alfabetico.

Forse tornerò e scriverò del codice per questo, ma questa è la chiave che stai cercando. Se il tuo codice soddisfa i criteri sopra indicati, eviterai automaticamente eventuali duplicati.

    
risposta data 31.05.2016 - 11:07
fonte

Leggi altre domande sui tag