Giocando a permutare i colori delle bandiere

Prendiamo la bandiera della Polonia: bianca (in alto) e rossa (in basso). Indichiamo questa configurazione con WR. Dati due simboli posso costruire 2! = 2 permutazioni: WR e RW. Posso però costruire anche la stringa WRW; questa permutazione ha la caratteristica di contenere entrambe le permutazioni precedenti: se prendo i primi due simboli ho WR, se prendo il secondo e il terzo ho RW. Possiamo naturalmente costruire la stringa WRRW, ma la stringa WRW è in un certo senso più sintetica.

Prendiamo ora la bandiera della Lituania: gialla (in alto), verde (in mezzo), rossa (in basso). Indichiamo questa configurazione con YGR. In questo caso le permutazioni possibili sono 3! = 6. Posso costruire una stringa di 3*6 = 18 simboli giustapponendo le sei permutazioni di YGR, ma se voglio creare una stringa “minima” mi servono molti meno simboli. Quanti? Se volete potete anche scriverla.

Visto che il problema precedente era molto semplice, ve ne propongo uno che lo è molto meno.

14 commenti (+aggiungi il tuo?)

  1. Mauro
    Dic 30, 2018 @ 21:27:44

    Cosa intendi con stringa “minima”?

  2. Nautilus
    Dic 30, 2018 @ 22:51:13

    @ Mauro

    La più corta possibile che permetta di soddisfare la condizione richiesta (nello specifico: estrarre da quella stringa tutte e sei le permutazioni di YGR).
    Nell’esempio della bandiera polacca WRRW e WRW sono entrambe stringhe ammissibili, perché da entrambe si possono estrarre le due permutazioni di WR. Solo che WRW è quella minima, mentre WRRW no.

  3. Mauro
    Dic 30, 2018 @ 22:56:29

    @ Nautilus

    OK, ora la domanda è chiara.

  4. Nautilus
    Dic 30, 2018 @ 23:00:42

    @ Mauro

    Il problema è talmente difficile che bisogna andare per tentativi. Ma questo lo spiegherò solo quando arriverà la soluzione corretta.

  5. shevathas
    Gen 02, 2019 @ 11:34:19

    io son riuscito a trovare questa YGRYGYRGY, 9 caratteri. (messaggio precedente errato)

  6. Nautilus
    Gen 02, 2019 @ 11:42:55

    @ shevathas

    E direi che sei stato mooolto bravo!

    Problemi di questa natura sono riconducibili al concetto di “superpermutazione”.
    Puoi approfondire qui: https://en.wikipedia.org/wiki/Superpermutation

    La cosa interessante è che questo è uno degli ambiti della matematica dove ci sono ancora problemi aperti.

  7. shevathas
    Gen 02, 2019 @ 11:56:16

    la soluzione l’ho trovata per costruzione; partendo dalla stringa di base si costruisce un albero creando due nodi foglia contenenti una lettera diversa dalla lettera finale; poi si verifica se la stringa ottenuta contiene tutte e sei le stringhe richieste, se no altrimenti si continua aggiungendo lettere.
    Ovviamente ho scritto un miniprogramma per farlo (almeno mi esercito con la programmazione e le strutture dati)

  8. Nautilus
    Gen 02, 2019 @ 12:15:41

    @ shevathas

    Interessante. Se vuoi puoi anche pubblicare qui il codice 🙂

  9. shevathas
    Gen 02, 2019 @ 13:04:33

    In perl, l’idea è di analizzare una stringa e se non è valida, cioè se non contiene tutte le permutazioni, la si allunga di un carattere e si mettono le stringhe così generate nella coda di analisi.

    Escludo a priori le stringhe con un carattere ripetuto come YGGR.

    Siccome controlla tutte le stringhe di lunghezza N prima di passare a quelle di lunghezza N+1 son sicuro che la stringa trovata è di lunghezza minima.
    Spero sia chiaro.

    #!/bin/perl
    use feature “say”;

    my $stringa = “YGR”;

    #array contenente le 6 permutazioni
    my @perm = (“YGR”, “YRG”, “GYR”, “GRY”, “RGY”, “RYG”);

    #la coda delle stringhe da controllare
    my @stringhe = ();

    #finché non trovi la stringa valida
    while(! test($stringa) )
    {
    #stampa la stringa analizzata (debug)
    say ($stringa.” “.test($stringa));

    #ripeti per le lettere “Y”,”G”,”R”
    for (“Y”,”G”,”R”)
    {
    #aggiungi in coda alla stringa Y, R e G
    $temp = $stringa.$_;
    #se non ci son lettere ripetute inserisci la stringa nella coda di quelle da controllare
    if($temp !~ /RR|GG|YY/)
    {
    push @stringhe, $temp;
    }
    }
    #pesca la nuova stringa da analizzare dall’inizio della coda
    $stringa = shift @stringhe;
    }

    say (“trovata: “.$stringa.” “.test($stringa));

  10. shevathas
    Gen 02, 2019 @ 13:06:14

    e questa è la funzione di test per verificare se la stringa contiene tutte le permutazioni

    #questa funzione verifica se nella stringa passata in input ci son tutte e 6 le occorrenze richieste
    sub test {
    my $t = shift @_;
    my $out = 1;
    #controlla brutalmente tutte le permutazioni, rende vero se ci son tutte altrimenti rende falso
    for (@perm) {
    #say($t =~ /$_/?”$_ – vero”:”$_ – falso”);
    $out = ($out and ($t =~ /$_/));
    }
    return $out;
    }

  11. Nautilus
    Gen 02, 2019 @ 13:13:12

    @ shevathas

    Linguaggio che conosco solo per sentito dire (io programmo in VBA), ma ho letto brevemente la pagina Wikipedia relativa. Si dice che è particolarmente indicato per la manipolazione dei testi.
    Lavorativamente parlando per cosa lo usi?

  12. shevathas
    Gen 02, 2019 @ 13:17:43

    se vuoi posso riscriverlo in VBA di access (mi tocca lavorare anche con quello); il perl lo uso lato server per qualche sistema automatico di acquisizione dati da internet (scarica il file, analizzalo, estrai i dati e sparalo sul DB) che come linguaggio di script per linux (la BASH mi da l’orticaria).
    Il perl l’avevo imparato anni ed anni fa quando lavoravo come HTML-ista, era ottimo per gestire le pagine statiche, ti lasciava più tempo per andare a caccia di brontosauri.

  13. shevathas
    Gen 02, 2019 @ 13:29:36

    VBA

    Option Explicit

    Sub Trova()

    Dim stringa As String

    Dim stringhe As New Collection

    stringa = “YGR”
    Do While Not (test_string(stringa))
    Debug.Print stringa & ” ” & test_string(stringa)
    Select Case Right(stringa, 1)
    Case “Y”
    stringhe.Add (stringa & “G”)
    stringhe.Add (stringa & “R”)
    Case “R”
    stringhe.Add (stringa & “G”)
    stringhe.Add (stringa & “Y”)
    Case “G”
    stringhe.Add (stringa & “Y”)
    stringhe.Add (stringa & “R”)
    End Select
    stringa = stringhe(1)
    stringhe.Remove 1
    Loop
    Debug.Print stringa & ” ” & test_string(stringa)
    End Sub

    Function test_string(s) As Boolean
    Dim perm
    perm = Array(“YGR”, “YRG”, “GYR”, “GRY”, “RGY”, “RYG”)
    Dim t
    Dim out As Boolean
    out = True
    For Each t In perm
    out = (out And (InStr(s, t)))
    Next
    test_string = out
    End Function

  14. Nautilus
    Gen 02, 2019 @ 13:37:19

    @ shevathas

    Non ce n’era bisogno, ti ho fatto lavorare per nulla 😀
    Grazie per la spiegazione!

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...