CIO Tech Eksperten IT-JOB IT-Kurser Events Podcast Søg

Log ind eller opret profil

Du kan også logge ind via nedenstående tjenester

__ak Nybegynder

15. november 2009 - 13:52 Der er 13 kommentarer og
1 løsning

Generere alle talkombinationer

Hej alle sammen

Jeg sidder og prøver at skrive et script jeg ikke rigtigt kan få til at virke efter hensigten - så har skrottet alt min kode, da jeg er ret sikker på jeg gik helt forkert til værks.

Det jeg gerne vil opnå er at ud fra en given streng, eks. "ab" vil jeg gerne generere alle mulige kombinationer af de tegn der er i strengen, og deres orden er _ikke_ ligegyldig. Altså er "ab" og "ba" to forskellige ord.

Jeg skal altså ende ud med:
aa
ab
bb
ba

osv. for større strenge.

Den skal meget gerne også generere strengen i alle mulige længder såfremt (længde>=2 && længde<=strlen("abc")).

Altså hvis strengen er "abcd" så skal den både generere "ab", "abc" og "abcd" i alle mulige kombinationer.

Og I behøver ikke påpege hvor mange kombinationer der kommer ud af det her når jeg kommer op i en større strenglængde - jeg har taget de overvejelser.

/ak

Synes godt om

Znak Nybegynder

15. november 2009 - 15:01 #1

Hej AK

Jeg har kigget lidt på det, og fundet frem til en lille løsning. Dog ved jeg ikke rigtig hvordan den skal kunne kompinere strengen i flere forskellige formater.

<?php /* START */

$str = "ab";
$strSize = strlen($str);

if ($strSize >= 2 AND $strSize <= 3)
{
// FOUND CHARTERS
for($i=0; $i <= $strSize-1; $i++)
{
if ($i == 0)
$numb[$i] = substr($str, $i, $i+1);
else
$numb[$i] = substr($str, $i, $i);
}
// PRINT CHARTERS
if ((array)$numb)
{
for($n=0; $n <= count($numb)-1; $n++)
echo "<span name=\"".$n."\">".$numb[$n]."</span><br>\n";
}

}

/* END */ ?>

Synes godt om

__ak Nybegynder

15. november 2009 - 15:07 #2

Hej Znak

Jeg har afprøvet din kode, og den gør ikke helt det jeg gerne vil have den til.
Jeg prøvede at give den "abcdefg" som input, og fjernede dit tjek

if ($strSize >= 2 AND $strSize <= 3)

og resultatet bliver følgende:
a
b
cd
def
efg
fg
g

Og det jeg gerne vil have, er alle kombinationer med de givne bogstaver.
For strenge der er 2 karakteret lange
For strenge der er 3 karakterer lange
...
For strenge der er 10 karakterer lange.

Synes godt om

repox Seniormester

15. november 2009 - 17:23 #3

At generere alle mulige kombinationer af en streng kaldes at permutate.

Et løsningsforslag:


    function permute($str) {
        if (strlen($str) < 2)
            return array($str);

        $permutations = array();
        $tail = substr($str, 1);

        foreach (permute($tail) as $permutation)
        {
            $length = strlen($permutation);
            for ($i = 0; $i <= $length; $i++)
                $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }

        return $permutations;
    }

Og for at bruge den, i den forbindelse du beskriver, har jeg brugt en while løkke:


    $string = "abcd";
    while(strlen($string) > 0)
    {
        $permutations = permute($string);
        foreach($permutations as $permutation)
            echo $permutation."\n";

        $string = substr($string, 0, -1);
    }

Synes godt om

__ak Nybegynder

15. november 2009 - 21:56 #4

Hej repox,

Og tusinde tak for din kode!!
Den ser ud til at virke ganske fortrineligt, dog er der en ting jeg er i tvivl om:
Med min egen "hovedregning" så skulle der være lige omkring 6,5 mio. muligheder:
10+
(10*9)+
(10*9*8)+
(10*9*8*7)+
(10*9*8*7*6)+
(10*9*8*7*6*5)+
(10*9*8*7*6*5*4)+
(10*9*8*7*6*5*4*3)+
(10*9*7*6*5*4*3*2)+
(10*9*8*7*6*5*4*3*2*1)
= ~ 6,5 mio.

Men dog giver dit resultat kun 4 mio. rækker i min database.

Er der nogen der kan sige om det er mig der regner forkert eller om det er koden der ikke gør det samme som mine udregninger?

- Andreas

Synes godt om

__ak Nybegynder

15. november 2009 - 22:04 #5

Og efter jeg lige rettede næst sidste linje i mit matematiske stykke får jeg:
(10*9*7*6*5*4*3*2)
rettet til:
(10*9*8*7*6*5*4*3*2)

9864100 ~ 10 mio. rækker.

alt hjælp er værdsat!

/ak

Synes godt om

__ak Nybegynder

15. november 2009 - 22:12 #6

Det ser umiddelbart ud for mig at de første kører alle tal igennem og generere alle kombinationer for alle 10 tegn.
Derefter fjerner den det sidste tal i strengen og genrerer derefter alle kombinationer med 9 tegn - dog mangler den her tallet 9, og næste gang mangler den tallene 9+8 osv osv.

Ret mig gerne hvis det er mig der er gal på den, eller hvis I har et andet løsningsforslag.

/ak

Synes godt om

acore Ekspert

16. november 2009 - 15:12 #7

Med to bogstaver ud af to angiver du 4 kombinationer i dit første indlæg ("aa", "ab", "ba" og "bb"), men din egen udregning i #4 giver kun 2*1 = 2 kombinationer.

Det rejser det grundlæggende spørgsmål, om det samme bogstav må være med flere gange?

Hvis det må, er det ikke en permutation (som _repox er inde på). Jeg vil gerne have det afklaret, før jeg evt giver et bud på koden.

Synes godt om

__ak Nybegynder

16. november 2009 - 20:26 #8

Hej acore,

Ja jeg kom selv i tanke om det samme issue tidligere idag.
Og svaret er, ja det samme tegn må gerne optræde flere gange i samme kombination - hvilket giver en helvedes masse flere kombinationer.

Jeg vil altså gerne.
- Generere alle kombinationer på 2 tegn med tallene 0-9
- Generere alle kombinationer på 3 tegn med tallene 0-9
osv osv.

Hvor tallenes orden _ikke_ er ligegyldig, og samme tal gerne må optræde flere gange i samme kombination.

/ak

Synes godt om

acore Ekspert

16. november 2009 - 20:55 #9

$letters = "abcd";
kombin($letters);

function kombin($letters)
{
$n = strlen($letters);

$ps = array();
for($i = 0; $i < $n; $i++)
$ps[$i] = 0;

for($no_letters = 2; $no_letters <= $n; $no_letters++)
do_kombin($letters, $ps, $n, $no_letters, 0);
}

function do_kombin(&$letters, &$ps, $n, $no_letters, $this)
{
if($this < $no_letters)
{
for($i = 0; $i < $n; $i++)
{
$ps[$this] = $i;
do_kombin($letters, $ps, $n, $no_letters, $this + 1);
}
}
else
{
for($i = 0; $i < $no_letters; $i++)
echo($letters[$ps[$i]]);

echo("<br />");
}
}

Synes godt om

acore Ekspert

16. november 2009 - 20:56 #10

Udskift "abcd" med de ønskede tegn - som alle skal være forskellige.

Synes godt om

__ak Nybegynder

17. november 2009 - 00:59 #11

Hej igen acore,

Dit script ser ud til at virke helt fantastisk, dog har jeg et lille problem.
Jeg forsøger at sætte kombinationerne ind i en database, med tilsvarende md5 hash, dog får jeg kun det første tegn i kombinationen ind i databasen.
Jeg har ændret din for løkke til følgende:

for($i = 0; $i < $no_letters; $i++) {
echo($letters[$ps[$i]]);
mysql_query("INSERT INTO `wordlist` SET `word`='".($letters[$ps[$i]])."', `hash`='".md5($letters[$ps[$i]])."'");
}
echo("\n");

Og i min kolonne "word" får jeg kun det første tal ind, eks:
0:cfcd208495d565ef66e7dff9f98764da
3:eccbc87e4b5ce2fe28308fd9f2a7baf3

osv. osv.
Min database er med:
`word` INT(11)
`hash` VARCHAR(32)

Kan du umiddelbart se hvad jeg gør forkert, for jeg kan ikke helt.

/ak

Synes godt om

acore Ekspert

17. november 2009 - 08:40 #12

Ja, det tror jeg.

'for' løkken skriver bogstaverne ud et ad gangen. Jeg vil foreslå, at erstatte den med:

for($i = 0, $s = ''; $i < $no_letters; $i++)
$s .= $letters[$ps[$i]];

mysql_query("INSERT INTO `wordlist` SET `word`='".$s."', `hash`='".$s."'");

altså generere tekst-strengen først og så indsætte den.

Synes godt om

__ak Nybegynder

17. november 2009 - 11:24 #13

acore,

Det ser ud som jeg har fået en 100% brugbar løsning.
Tusinde tak for hjælpen, det er fantastisk!

/ak

Synes godt om

acore Ekspert

17. november 2009 - 11:28 #14

Det var godt at høre. Tak for tilbagemeldingen.

Synes godt om

Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Følg dette spørgsmål

Opret Preview

Webudvikling kurser

Vi tilbyder markedets bedste kurser inden for webudvikling

Se alle Webudvikling kurser

Flere spørgsmål fra PHP kategorien

Titel	Indlæg	Oprettet	Seneste aktivitet
Hent array key Af nemlig i PHP	3	17/05/202415:22	17/05/202416:30
iCal-feed og import til google kalender driller Af nemlig i PHP	11	09/05/202417:49	10/05/202421:28
Adgang til vandaflæsningsdata Af nemlig i PHP	4	22/04/202422:04	30/04/202421:08
Vælg post rækkefølge Af Mojo_dk i PHP	3	06/04/202418:40	07/04/202412:20
Hjælp til PHP Af Friis77 i PHP	5	11/02/202419:58	12/02/202407:55

Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten

Seneste artiklerRSS