[alg]Verschillende lettercombinaties genereren?

[PanMan]

Hoi!
Ik zit al een tijdje hiernaar te staren, maar ik kom er niet uit.
Stel, ik heb een aantal letters. Daaruit wil ik alle mogelijke combinaties (tot een max aan lengte) genereren. Letters mogen 1 of meer keer voorkomen, maar niet meerdere keren achter elkaar.
Stel, m'n letters zijn (geheel willekeurig ) p,a,n,m,a,n en ik wil codes van 3 letters, dan mag nmn wel, maar ppm niet
Ik zit hier echt ontzettend te klooien, en er is vast een (relatief) simpele oplossing, maar ik kom er niet uit. Iemand een opzetje in de goede richting?
Ik kan een loopje maken dat de letters eruit gooit, maar dan pak ik geen herhalingen.

[JHS]

Loopje maken dat de letters eruitgooid, en vlak voor je hem eruitgooien controleren of hij niet gelijk is aan de vorige, zoja, niet uitspugen en het loopje 1x extra doorlopen ($i ophogen), zonee gewoon verdergaan .

[Creepy]

Zo moeilijk is dat toch niet? Bepaal random een letter uit de gegeven letters. Bij de tweede letter en verder check je of de vorige letter niet hetzelfde is. Zo ja, start opnieuw, zo nee, letter neerzetten en start opnieuw totdat de gewenste lengte is bereikt.

Of wil je misschien alle mogelijke combinaties genereren? Zoek dan eens op "permutatie"

[ Voor 6% gewijzigd door Creepy op 03-01-2006 17:22 ]

[Soultaker]

Geen wonder dat het je het niet kunt implementeren, als je niet eens duidelijk kunt formuleren waar je naartoe wil.

Als je 'panman' als invoer hebt, wat betekent de volgorde van letters dan voor de mogelijke uitvoer? Is het van belang dat de 'a' twee keer voorkomt en de 'p' maar één keer?

Schrijf desnoods een voorbeeld helemaal uit. Zo is het absoluut niet duidelijk waar je heen wilt.

[n3ck]

makkelijkste met recursie.

[PanMan]

Soultaker schreef op dinsdag 03 januari 2006 @ 17:35:
Geen wonder dat het je het niet kunt implementeren, als je niet eens duidelijk kunt formuleren waar je naartoe wil.

Als je 'panman' als invoer hebt, wat betekent de volgorde van letters dan voor de mogelijke uitvoer? Is het van belang dat de 'a' twee keer voorkomt en de 'p' maar één keer?

Schrijf desnoods een voorbeeld helemaal uit. Zo is het absoluut niet duidelijk waar je heen wilt.

Sorry als ik onduidelijk was, maar ik weet zeker waar ik heen wil
Stel, ik heb als input PAN, dan wil ik alle mogelijke combinaties genereren, met als enige eis dat er nooit 2x dezelfde letter achter elkaar staat
Dus:
PAN
NAP
APN
NAN
PAP
APA
ANA
enz.
maar NIET
AAP
PPA
NNA
NNP
etc
Ik wil dus alle mogelijke permutaties (dat woord zocht ik inderdaad!), behalve diegene waar 2x dezelfde letter achter elkaar staat. Maar met alle lukt het waarschijnlijk wel om die met dubbele letters eruit te vegen.

[prototype]

Wat je kan doen is een letterverzameling bijhouden, b.v. in een array. Vervolgens maak je een lus, waarvan het aantal iteraties afhankelijk is van de lengte van het woord dat je wil genereren. Dan binnen elke iteratie moet je bijhouden wat de vorige letter was, i.e. de key van de letter uit de array. Deze mag namelijk niet nog een keer gekozen worden, als deze een 'zinnige' (vanaf 0 t/m 25) waarde X heeft; initialiseer 'm buiten de lus met een waarde die het nooit kan aannemen, b.v. -1, of null wanneer je een taal gebruikt die nullable types ondersteund. Dit is namelijk evt handig om te bepalen of je nu te maken hebt met de eerste iteratie of met een itteratie tussen de eerste en max lengte.
Dan, zou je een random reeel getal R kunnen genereren tussen de 0 en de 1. Afhankelijk van de integer representatie van R (0 of 1), ga je dan de te kiezen random letter ONDER X ( namelijk {LETTER | LETTER >= 0 EN LETTER < X} ), danwel BOVEN X (namelijk {LETTER | LETTER > X EN LETTER < 26}) verkrijgen. Voor de eerste iteratie heb je dan de hele range van 0 t/m 25.
LETTER kan je bepalen mbv R, door deze te vermenigvuldigen mbv numeric promotion met je 'interval' (boven of onder X), en dan de integer representatie nemen van de uitkomst daarvan.
Vervolgens nadat je bepaalt hebt welke letter het gaat worden, assign je LETTER aan X, i.e. X = LETTER en ga je door naar de volgende iteratie net zo lang tot je de max lengte van je woord bereikt hebt.

[ Voor 29% gewijzigd door prototype op 04-01-2006 01:32 ]

[Woy]

heel simpel je wilt dus elke keer een random letter uit je input string hebben. Dit wil je x maal herhalen. De enige extra voorwaarde is dat de letter die je kiest niet de zelfde is als de vorige. In pseudo code doe je dan heel makkelijk.

code:

inputString = 'blablaadafdsa'
outputString = '';
currentChar = null;
for( 0 to x )
    currentChar = GetRandomChar( inputString, currentChar )
    outputString += currentChar

function GetRandomChar( stringToPickFrom, excludeChar )
    chosenChar = null
    while( chosenChar == null || chosenChar == excludeChar )
        chosenChar = stringToPickFrom[ random ]
    return chosenChar
end function

[ Voor 7% gewijzigd door Woy op 04-01-2006 09:40 ]

[mrBussy]

Als ik het goed begrijp wil hij ALLE mogelijkheden. Daarmee is het gebruik van Random dus al niet echt nodig omdat je daarmee niet echt allee combinaties hoeft te vinden. Tenzij je daar weer alle controle voor inbouwd etc. Tevens vraagt TS daar ook niet naar.

Wat ik zou doen is het volgende:

code:

StringLength := 5
CharSet := "abc"

Generate("", "")

Sub Generate(CurChar, CurString)

String := ""

       For Each Char In CharSet

            IF Char != CurChar 
               String := CurString & Char
               IF(Length(String) = StringLength)
                  Write(String)
               Else
                   Generate(Char, String)
               EndIF
            EndIf
       NEXT FOR
End Sub

[ Voor 8% gewijzigd door mrBussy op 04-01-2006 09:56 ]

[Verwijderd]

Daaruit wil ik alle mogelijke combinaties (tot een max aan lengte) genereren.

Als je ALLE combinaties wilt hebben, dan moet je niet met random getallen werken.
Loop gewoon alles af, en check daarna of aan de voorwaarde is voldaan.

Voor de duidelijkheid laat ik het zien in pseudocode, met het domste algoritme mogelijk. Je kunt het genereren van alle combinaties ook in 1 loop verpakken, maar dat is afhankelijk van de programeertaal hoe je dat doet.

Maak eerst een functie die checkt of er verboden combinaties in staan:

code:

check=function(lettercombi) 
{
verboden=false

loop i=1 tot length(lettercombi)-1
if lettercombi[i]==lettercombi[i+1] then verboden=true
next
}

Vervolgens loop je alle letters af:
stel je wilt tot 3 letters lengte, en je hebt 26 letters

code:

1 letter:

loop i=1 tot 26
res_1[i] = letter [i]
next


2 letters

k=1
loop i=1 tot 26
loop j=1 tot 26

temp=letter [i] & letter[j]

if (check( temp  ) == false) then 
  res_2[k] =  temp
  k=k+1
endif

next
next


3 letters

k=1
loop i=1 tot 26
loop j=1 tot 26
loop l=1 tot 26

temp=letter [i] & letter[j] & letter[l]

if (check( temp  ) == false) then 
  res_2[k] =  temp
  k=k+1
endif

next
next
next

[ Voor 10% gewijzigd door Verwijderd op 04-01-2006 10:07 ]

[PanMan]

Ah! Ik heb er een beetje aan lopen sleutelen, maar nu werkt het iig!
Ik heb nu deze code, in PHP:

PHP:

<?php
function check($lettercombi){

for ($i=0;$i<strlen($lettercombi)-1;$i++) {
#echo "$i-Testing: $lettercombi: -", $lettercombi[$i],"-VS-", $lettercombi[$i+1],"<br>"; 
    if ($lettercombi[$i] == $lettercombi[$i+1]) {
    return(false);}
}
return(true);
}

$letters='panman'; 
#echo $letters[3];
echo strlen($letters);
for ($i=0;$i<strlen($letters);$i++) {
for ($j=0;$j<strlen($letters);$j++) {
for ($k=0;$k<strlen($letters);$k++) {

$temp=$letters[$i].$letters[$j].$letters[$k];

if (check($temp)) {$res2[]=$temp;}

}
}
}

echo "<pre>";
var_dump($res2);
?>

Die werkt, dus dat is fijn! Nu ga ik nog even kijken of ik de recursieve ook aan de praat kan krijgen, want ik wil natuurlijk eigenlijk meer dan 3 letters kunnen genereren, zonder nogmeer loopjes...

[prototype]

Wow, ik was duidelijk aan de crack op dat tijdstip, niet goed de vraag gelezen, my bad (gelukkig was ik niet de enige).

[ Voor 3% gewijzigd door prototype op 04-01-2006 16:28 ]

[PanMan]

Hrmz, ik krijg de recusieve nog niet aan de praat. Hij geeft nu dit:
string(4) "papa"
[1]=>
string(4) "papn"
[2]=>
string(4) "papm"
[3]=>
string(4) "papa"
[4]=>
string(4) "papn"

PHP:

<?php
$letters=array('p','a','n','m','a','n'); 


$StringLength=4;
Generate("", "");

function Generate($CurChar, $CurString) {
$temp="";
global $letters, $StringLength;
    foreach ($letters as $char) {
echo "Letter: ", $char, "<br>", $a++; 
            if ($char!=$CurChar ) {
               $temp= $CurString .$char;
               echo "temp: ", $temp,"- togoto:", $StringLength, "- lengthnu:", strlen($temp);
               
               if(strlen($temp)>=$StringLength) {
                  echo "<hr>Stoppen:", $temp,"<hr>";
                  $GLOBALS[res3][]=$temp;
               } else {
                   Generate($char, $temp);
               }
            }
       }
}
var_dump($GLOBALS[res3]);
?>

[Verwijderd]

Hier ooit iets dat is ik Fortran gebruikt heb.

Het werkt niet met letters, maar met getallen. Dat kun je zo veranderen door elk getal dat eruit komt een index te laten zijn naar de array met letters. Verder is het iets algemener omdat elke kolom een ander aantal 'letters' mag hebben.

Input:
maxcat: een array met lengte van aantal letters, met in elke cell het maximaal aantal letters.

bv je wilt alle woorden maken van 4 letters lang, en je hebt 8 verschilllende letters, dan is maxcat (8,8,8,8)

Output:
mindex

de array met alle combinaties.

vb met bovenstaande getallen is mindex een array van 8^4 bij 4

code:

subroutine multi_index (maxcat,mindex)

!index a contingency table in an anti lexicographical manner

implicit none

integer, intent(out),dimension(:,:) ::mindex
integer, intent(in),dimension(:)    ::maxcat
logical                        ::more=.false.
integer, dimension(size(maxcat))    ::mindex1
integer                         ::i


    do i=1,product(maxcat)
        call index_next (maxcat,mindex1,more)
        mindex(i,:)=mindex1
    enddo

    
contains

    subroutine index_next(maxcat, mindex, more)

    implicit none

    integer,dimension(:)             :: maxcat
    integer                          :: i,inc
    integer, dimension(size(maxcat)) :: mindex
    logical more

        if (more==.false. ) then
            mindex(1:size(maxcat)) = 1
        else
            inc = 0

            do
                inc = inc + 1
                    if ( mindex(inc) < maxcat(inc) )  exit
                mindex(inc) = 1
            end do
            mindex(inc) = mindex(inc) + 1
        end if

        more = .false.
        do i = 1, size(maxcat)
            if ( mindex(i) < maxcat(i) )  more = .true.
        end do

    end subroutine



end subroutine