Samtlige kombinationer
Jimmy
Jeg skal lave mig et stykke kode, som udskriver samtlige kombinationer af en
række input.
Vi kunne eks. have "a", "b" og "c".
Det ville kunne resultere i
abc
acb
bac
bca
cab
cba
Hvordan kunne man kode noget der kunne lave den slags?
Stikord og ideer er meget velkomne - jeg forventer ikke at få serveret et
stykke færdigt kode, men jeg kan ikke rigtigt komme igang med det.
Mvh
Jimmy
Torben Brandt
1) "samtlige kombinationer" af én enkelt input er bare inputtet
2) Hvert "enkelt input" skal sættes før "samtlige kombinationer af resten af
inputene"
Denne er nok især bedst, hvis antallet an input er variabelt. Hvis antallet er
fast, kan man nok udnytte at dette tal er fast, og starte ud fra det.
Der er helt sikkert rigtig mange andre måder at gøre det på, men dette var lige
det som først faldt mig ind...
mvh Torben
--
Vil du lære at kode HTML, XHTML, CSS, SSI eller ASP ???
- Pædagogiske tutorials på dansk
- Kom godt i gang med koderne
KLIK HER! => http://www.html.dk/tutorials
Jens Gyldenkærne Clausen
> Jeg skal lave mig et stykke kode, som udskriver samtlige
> kombinationer af en række input.
> Hvordan kunne man kode noget der kunne lave den slags?
Hvis du har adgang til en database - og din række har samme længde
- kan du benytte CROSS JOIN til at finde alle kombinationer.
Eksempel (skrevet i MSSQL, men det skulle være til at ændre til
andre databaser):
---------------------
USE tempdb
go
IF EXISTS (SELECT * FROM dbo.sysobjects where id =
object_id(N'[dbo].[tbl_kombi]') AND OBJECTPROPERTY(id,
N'IsUserTable') = 1)
DROP TABLE tbl_kombi
GO
CREATE TABLE tbl_kombi (input char(1))
GO
INSERT INTO tbl_kombi VALUES ('a')
INSERT INTO tbl_kombi VALUES ('b')
INSERT INTO tbl_kombi VALUES ('c')
SELECT t1.input + t2.input + t3.input as kombinationer
FROM tbl_kombi t1
CROSS JOIN tbl_kombi t2
CROSS JOIN tbl_kombi t3
---------------------
Processen kan evt. automatiseres, således at der udføres præcis
lige så mange CROSS JOIN's som der er rækker i kildetabellen.
--
Jens Gyldenkærne Clausen
Svar venligst under det du citerer, og citer kun det der er
nødvendigt for at forstå dit svar i sammenhængen. Se hvorfor og
hvordan på http://usenet.dk/netikette/citatteknik.html
Jimmy
news:Xns92A9664E...@gyrosmod.dtext.news.tele.dk...
> Jimmy skrev:
>
> > Jeg skal lave mig et stykke kode, som udskriver samtlige
> > kombinationer af en række input.
>
> > Hvordan kunne man kode noget der kunne lave den slags?
>
> Hvis du har adgang til en database - og din række har samme længde
> - kan du benytte CROSS JOIN til at finde alle kombinationer.
Den havde jeg også selv tænkt på.
Dog ikke så avanceret som dit :-)
Men - abc var kun en tænkt eksempel.
Input har varierende længder.
Kan man bruge VARCHAR(255) i stedet for CHAR(1)?
Mvh
Jimmy
Sjakal
være ligemeget ;)
<script language="JavaScript">
function getSolutions(aStr,aSolution)
{
for (var i=0, tmpstr=""; i<aStr.length; i++)
{
if (aSolution==null)
{
tmpstr=aStr.charAt(i);
getSolutions(aStr,tmpstr);
}
else
{
if (aSolution.indexOf(aStr.charAt(i))==-1)
{
tmpstr=aSolution+aStr.charAt(i);
getSolutions(aStr,tmpstr);
}
}
}
if (tmpstr.length==aStr.length) document.write(tmpstr+"<br>");
}
getSolutions("ACD");
</script>
"Jimmy" <spo...@efter.den> wrote in message
news:9i%q9.84$6T....@news.get2net.dk...
Jimmy
news:3dad3868$0$22022$edfa...@dspool01.news.tele.dk...
> Her er en løsning jeg kogte sammen hurtigt, dog i javascript. Men det
burde
> være ligemeget ;)
Ja helt enig.
Det virker fint, men jeg havde vist glemt at sige at input har varierende
længder.
Kunne man eks ikke lave en komma-separeret streng, konvertere den til et
array og så løbe arrayet igennem?
Jeg er ikke den store JS-koder så derfor spørger jeg :-)
Mvh
Jimmy
Jens Gyldenkærne Clausen
> Den havde jeg også selv tænkt på.
> Dog ikke så avanceret som dit :-)
>
> Men - abc var kun en tænkt eksempel.
> Input har varierende længder.
> Kan man bruge VARCHAR(255) i stedet for CHAR(1)?
Det kan du godt. Der kombineres kun elementer, ikke bogstaver - det
vil sige at følgende modificerede eksempel:
---
CREATE TABLE tbl_kombi (input varchar(255))
GO
INSERT INTO tbl_kombi VALUES ('abe')
INSERT INTO tbl_kombi VALUES ('bavian')
INSERT INTO tbl_kombi VALUES ('cykel')
SELECT t1.input + t2.input + t3.input as kombinationer
FROM tbl_kombi t1
CROSS JOIN tbl_kombi t2
CROSS JOIN tbl_kombi t3
---
Giver postsættet:
abeabeabe
abebavianabe
abecykelabe
abeabebavian
abebavianbavian
abecykelbavian
abeabecykel
abebaviancykel
abecykelcykel
...etc.
Hvis du vil have elementer ud hver for sig kan du bare ændre i
feltlisten.
Sjakal
-----
Her er en løsning jeg kogte sammen hurtigt, dog i javascript. Men det burde
være ligemeget ;)
<script language="JavaScript">
function getSolutions(aStr,aSolution)
{
for (var i=0, tmpstr=""; i<aStr.length; i++)
{
if (aSolution==null)
{
tmpstr=aStr.charAt(i);
getSolutions(aStr,tmpstr);
}
else
{
if (aSolution.indexOf(aStr.charAt(i))==-1)
{
tmpstr=aSolution+aStr.charAt(i);
getSolutions(aStr,tmpstr);
}
}
}
if (tmpstr.length==aStr.length) document.write(tmpstr+"<br>");
}
getSolutions("ACD");
</script>
"Jimmy" <spo...@efter.den> wrote in message
news:9i%q9.84$6T....@news.get2net.dk...
"Jimmy" <spo...@efter.den> wrote in message
news:9i%q9.84$6T....@news.get2net.dk...
Jens Gyldenkærne Clausen
> Kunne man eks ikke lave en komma-separeret streng, konvertere
> den til et array og så løbe arrayet igennem?
Jo, det skulle være muligt.
> Jeg er ikke den store JS-koder så derfor spørger jeg :-)
Prøv evt. i clientside-gruppen.
Jens Gyldenkærne Clausen
> Hmm, prøver lige igen.... Ser ik ud til at være sendt?
Men det var den
(<news:3dad3868$0$22022$edfa...@dspool01.news.tele.dk>).
Der kan godt gå lidt tid før et indlæg dukker op (ikke mindst hvis
man sender gennem TDC).
PS: Det er lettere at følge dine indlæg hvis du svarer nedenunder
det du citerer, og i øvrigt kun citerer det der er nødvendigt for
at forstå sammenhængen. Se evt. linket i min signatur.
Jimmy
> CREATE TABLE tbl_kombi (input varchar(255))
> GO
> INSERT INTO tbl_kombi VALUES ('abe')
> INSERT INTO tbl_kombi VALUES ('bavian')
> INSERT INTO tbl_kombi VALUES ('cykel')
>
> SELECT t1.input + t2.input + t3.input as kombinationer
> FROM tbl_kombi t1
> CROSS JOIN tbl_kombi t2
> CROSS JOIN tbl_kombi t3
Jeg har forsøgt det på en MySQL som returnerer 27 rækker med 0 i dem alle...
Må se om jeg ikke kan finde mig en MSSQL-prompt et sted så det vil virke.
Tak for svaret i øvrigt.
Mvh
Jimmy
Jakob Andersen
Jeg har lige strikket nedenstående sammen:
> Jeg skal lave mig et stykke kode, som udskriver samtlige kombinationer af
en
> række input.
>
> Vi kunne eks. have "a", "b" og "c".
<%
Option Explicit
Sub PrintMuligheder( strChars )
Dim tmpArray
tmpArray = Split( strChars , "," )
Response.Write("Der er " & (UBound( tmpArray ) + 1)^(UBound( tmpArray ) +
1) & " muligheder.<br />")
Dim strLoops, strPrint, strEnd, i
For i = 0 To UBound(tmpArray)
strLoops = strLoops & "For " & tmpArray(i) & " = 0 To UBound(tmpArray)" &
vbcrlf
strPrint = strPrint & "tmpArray(" & tmpArray(i) & ") & "
strEnd = strEnd & "Next" & vbcrlf
Next
Dim Result
Execute(strLoops & "Result = Result & " & strPrint & """<br />""" & vbcrlf
& strEnd)
Response.Write( Result )
End Sub
PrintMuligheder "a,b,c"
%>
Men pas nu på det er en eksponentiel kurve, bare du sender fem
inputparametre kommer du op på 3125 løsninger
--
Jakob Andersen
Jakob Andersen
> Jeg har lige strikket nedenstående sammen:
Undskylder, der gik lige kuk i min citering..
--
Jakob Andersen
Jakob Andersen
> Interessant - det virker så længe man ikke har to ens input og der ikke er
> rene tal i input.
Det er som du selv siger fordi at inputtet bliver som tællere i loopet.
> Har indtryk af, at det blot er at redigere i koden, så input ikke anvendes
> som variabel-navn.
Jeps :-)
--
Jakob Andersen
Jimmy
news:aojik5$5pm$1...@news.cybercity.dk...
> "Jimmy" <spo...@efter.den> wrote
> Jeg har lige strikket nedenstående sammen:
> > Jeg skal lave mig et stykke kode, som udskriver samtlige kombinationer
af
> en
> > række input.
> >
> > Vi kunne eks. have "a", "b" og "c".
>
>
Interessant - det virker så længe man ikke har to ens input og der ikke er
rene tal i input.
Har indtryk af, at det blot er at redigere i koden, så input ikke anvendes
som variabel-navn.
> Men pas nu på det er en eksponentiel kurve, bare du sender fem
> inputparametre kommer du op på 3125 løsninger
HEHE ja det går stærkt...
Tak for svaret,
Jimmy
Sjakal
"Jimmy" <spo...@efter.den> wrote in message
news:JRar9.845$Xw1...@news.get2net.dk...
Allan Ebdrup
> Jeg skal lave mig et stykke kode, som udskriver samtlige kombinationer af
en
> række input.
> Vi kunne eks. have "a", "b" og "c".
> Det ville kunne resultere i
>
> abc
> acb
> bac
> bca
> cab
> cba
Hej Jimmy
Jeg synes din opgave var en sjov lille udfordring så jeg har lavet koden,
den fungerer rekursivt.
Resultatet er et array af arrays af strings, så jeg har levet en lille
funktion til at udskrive den datastruktur (WriteArrayArray), resten af koden
har kommentare der burde være mulige at gennemskue hvis du har arbejdet med
rekursion før.
Koden kan optimeres, men det ville være noget nemmere at gøre i et "Rigtigt"
programmeringssprog fordi VBScript er meget tungt at arbejde med når det
kommer til advancerede datastrukture, derudover begynder det også at slå
igennem at det er et fortolket sprog hvis du skal lave "større"
kombinationer. Tidskompleksiteten er O(N! * N), den burde kunne reduceres
til noget i stil med O(N!*Log(N)), som stadig er ret slem, men der opstår jo
hurtigt mange kombinationer og du skal bruge dem allesammen ikke. Hvis du
bare skal checke om en enkelt given kombination er mulig givet en række data
kan du sikkert lave noget der er O(N*Log(N)) el. lig.
For at udregne factorial har jeg brugt den simple rekursive implementation,
den er ikke effektiv hvis du skal arbejde med store datasæt kan denne
optimeres:
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
En sidste kommentar: Jeg går ud fra at alle arrays er 0 (nul) indekseret.
Nå nok snak, her er koden:
Dim aIn, aOut
aIn = Array("a", "b", "c", "d")
aOut = CrossJoin(aIn)
Response.Write "Result:<br>"
call WriteArrayArray(aOut)
function CrossJoin(ByVal paIn)
Dim aShortIn, strLastElement, aCombine, aOut, intInLength, aTmp, i, j, k, l
intInLength = (UBound(paIn)-LBound(paIn)+1) 'get length og array
'with an empty array we do not know what to return
if intInLength<=0 then exit function
'with an array of length 1 we return the array
if intInLength = 1 then
aOut = Array(paIn)
else
'with an array og length 2 or greater we calculate the combinations
recursively
'create an array with room for all the combinations
Redim aOut(factorial(intInLength)-1)
'get last element
strLastElement = paIn(UBound(paIn))
'remove last element
aShortIn = paIn
Redim Preserve aShortIn(intInLength-2)
'get all combinations for array without last element
aCombine = CrossJoin(aShortIn)
'for each combination for array without last element...
m=0
Redim aTmp(intInLength-1)
for i=0 to UBound(aCombine)
'...insert lastelement into combination at every possible position
for j=0 to (UBound(aCombine(i))+1)
'generate array with lastelement at at the j'th position
for k=0 to UBound(aCombine(i))+1
if k<j then
aTmp(k) = aCombine(i)(k)
elseif k>j then
aTmp(k) = aCombine(i)(k-1)
else
aTmp(k) = strLastElement
end if
next
aOut(m) = aTmp
m = m+1
next
next
end if
CrossJoin = aOut
end function
Function factorial(n)
dim i, intOut
intOut = 1
for i = 1 to n
intOut = intOut * i
next
factorial = intOut
End Function
Function WriteArrayArray(paaIn)
Dim i
for i=0 to UBound(paaIn)
Response.Write i & " : " & Join((paaIn(i)), ",") & "<br>"
next
End function
Sjakal
"Jimmy" <spo...@efter.den> wrote in message
news:JRar9.845$Xw1...@news.get2net.dk...
Allan Ebdrup
news:aojl66$8r3$1...@news.cybercity.dk...
> Hej Jimmy
> Jeg synes din opgave var en sjov lille udfordring så jeg har lavet koden,
> den fungerer rekursivt.
Nå for dæwlen' der var vidst mange andre end mig der synes det var en sjov
lille opgave, men det ser ud til at jeg er den eneste der har lavet en
løsning der arbejder med arrays og derfor ikke er afhængig af en unik
seperator (kan arbejde med kombination af vilkårlige elementer). Håber den
kan bruges...
MVH
Allan Ebdrup, 10-4 ApS
http://www.aspfastforum.com/aspfastforum/
Jakob Andersen
> Nå for dæwlen' der var vidst mange andre end mig der synes det var en sjov
> lille opgave, men det ser ud til at jeg er den eneste der har lavet en
> løsning der arbejder med arrays og derfor ikke er afhængig af en unik
> seperator (kan arbejde med kombination af vilkårlige elementer). Håber den
> kan bruges...
Men den returnerer ikke det korrekte resultater eller er det bare mig der
ikke fatter en dyt?
--
Jakob Andersen
Allan Ebdrup
> Men den returnerer ikke det korrekte resultater eller er det bare mig der
> ikke fatter en dyt?
Det vil jeg da mene at den gør. Hvorfor mener du at der er en fejl? Er der
en kombination der mangler? Du bliver nød til at uddybe hvis jeg skal kunne
svare...
MVH
Allan
Jimmy
> news:9i%q9.84$6T....@news.get2net.dk...
> > Jeg skal lave mig et stykke kode, som udskriver samtlige kombinationer
af
> en
> > række input.
> > Vi kunne eks. have "a", "b" og "c".
> Jeg synes din opgave var en sjov lille udfordring så jeg har lavet koden,
> den fungerer rekursivt.
> Resultatet er et array af arrays af strings, så jeg har levet en lille
> funktion til at udskrive den datastruktur (WriteArrayArray), resten af
koden
> har kommentare der burde være mulige at gennemskue hvis du har arbejdet
med
> rekursion før.
Tak for svaret.
Det var en ordentlig omgang :-)
Det virker perfekt.
Gør præcis hvad jeg har brug for.
I mit tilfælde skal jeg ikke bruge kombinationer, hvor samme input genbruges
og jeg sparer derfor en stor mængde resultater, når jeg ikke skal have "aaa"
og "aab" osv.
I øvrigt - tak til alle for indsatsen!
Mvh
Jimmy
Allan Ebdrup
> Tak for svaret.
> Det var en ordentlig omgang :-)
>
> Det virker perfekt.
> Gør præcis hvad jeg har brug for.
> I mit tilfælde skal jeg ikke bruge kombinationer, hvor samme input
genbruges
> og jeg sparer derfor en stor mængde resultater, når jeg ikke skal have
"aaa"
> og "aab" osv.
Ahhh, det er det der er blevet misforståer. Til en anden god gang kan du
kalde det at:
"Generere alle mulige permutationer af et array".
At permutere er bare at bytte om på elementer. Dvs. du vil gerne have er
alle mulige omrokering af elementerne, hvor du har kun de elementer du
starter med. Hvis du har 2 "a"-er til at starte med skal alle resultat
strenge indeholde præcist 2 "a"-er, hverken mere eller mindre.
MVH
Alan Ebdrup
Jakob Andersen
> Det vil jeg da mene at den gør. Hvorfor mener du at der er en fejl? Er der
> en kombination der mangler? Du bliver nød til at uddybe hvis jeg skal
kunne
> svare...
Du har svaret andet steds i tråden, jeg må indrømme jeg heller ikke lige
tænkte mig om.
--
Jakob Andersen
Allan Ebdrup
http://www.geocities.com/permute_it/index.html
Jeg har ikke lige analyseret tidskompleksiteten, men den ser ud til at være
O(N!), og den kører hurtigere end den rekursive løsning jeg lavede, specielt
hvis N bliver stor.
Jeg har heller ikke bevist at den virker, og der er ikke et bevis på
hjemmesiden.
Så du må selv igang med blyanten hvis du vil bevise at den virker og har
O(N!) tidskompleksitet
Dim aIn, aOut
aOut = CrossJoin2(aIn)
Response.Write "Result:<br>"
call WriteArrayArray(aOut)
'Iterativ
Function CrossJoin2(ByVal paIn)
Dim a, p, i, j, intPos, N, aOut, tmp
a = paIn
intPos = 0
'get length og array
N = (UBound(paIn)-LBound(paIn)+1)
'make output array ready
Redim aOut(factorial(N)-1)
'create an integer array p[] of size N+1 to control the iteration
Redim p(N)
'initialize p[0] to 0, p[1] to 1, p[2] to 2, ..., p[N] to N
for i=0 to UBound(p)
p(i) = i
next
'initialize index variable i to 1
i=1
do while (i < N)
p(i) = p(i)-1
'if i is odd, then let j = p[i] otherwise let j = 0
if (i mod 2)=1 then
j = p(i)
else
j=0
end if
'save current permutation in aOut
aOut(intPos) = a
intPos = intPos+1
'swap(a[j], a[i])
tmp = a(j)
a(j) = a(i)
a(i) = tmp
'let i = 1
i=1
do while p(i)=0
p(i) = i
i = i+1
loop
loop
aOut(intPos) = a
CrossJoin2 = aOut