Herhaalde partiele permutaties
Herhaalde partiele permutaties
Beste lezers,
Ik zit in mijn maag met dit probleem:
De achterliggende gedacht is dat in een volledig netwerk met n aantal knopen verschillende volgorden (routes) worden gemaakt.De verzameling van alle volgordes is gelijk aan het aantal knopen in het netwerk. M.a.w. elke knoop wordt enkel en alleen één keer bezocht.
Als je maar 1 route mag maken dan zijn er n! verschillende permutaties.
Als je 2 routes mag maken dan is het al wat lastiger:
Voor de eerste route kun je k knopen uit n kiezen, dit heet een variatie en er zijn dan n!/(n-k)! partiele permutaties voor elke keuze van k. Voor de tweede route is de verzameling knopen nu n-k groot en omdat alle knopen moeten worden bezocht zijn het aantal mogelijkheden dan ook (n-k)!.
Voor twee routes zijn er dus SOM(k=1 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=1 tot n) n! verschillende mogelijkheden.
Mijn probleem is nu: wat als je n routes mag maken, hoeveel mogelijkheden zijn er nu? Daarbij mag het voorkomen dat een route geen enkele knoop bezoekt zolang alle knopen maar wel door een route worden bezocht.
Wie kan mij helpen? Ik ben gisteren tot laat in de nacht doorgegaan maar geen succes. Bij voorbaat dank!
ps: Sorry voor de vage wiskundige notaties maar ik weet niet hoe je dat op een nette manier op het forum kan doen.
Ik zit in mijn maag met dit probleem:
De achterliggende gedacht is dat in een volledig netwerk met n aantal knopen verschillende volgorden (routes) worden gemaakt.De verzameling van alle volgordes is gelijk aan het aantal knopen in het netwerk. M.a.w. elke knoop wordt enkel en alleen één keer bezocht.
Als je maar 1 route mag maken dan zijn er n! verschillende permutaties.
Als je 2 routes mag maken dan is het al wat lastiger:
Voor de eerste route kun je k knopen uit n kiezen, dit heet een variatie en er zijn dan n!/(n-k)! partiele permutaties voor elke keuze van k. Voor de tweede route is de verzameling knopen nu n-k groot en omdat alle knopen moeten worden bezocht zijn het aantal mogelijkheden dan ook (n-k)!.
Voor twee routes zijn er dus SOM(k=1 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=1 tot n) n! verschillende mogelijkheden.
Mijn probleem is nu: wat als je n routes mag maken, hoeveel mogelijkheden zijn er nu? Daarbij mag het voorkomen dat een route geen enkele knoop bezoekt zolang alle knopen maar wel door een route worden bezocht.
Wie kan mij helpen? Ik ben gisteren tot laat in de nacht doorgegaan maar geen succes. Bij voorbaat dank!
ps: Sorry voor de vage wiskundige notaties maar ik weet niet hoe je dat op een nette manier op het forum kan doen.
Re: Herhaalde partiele permutaties
Als een route nul knopen mag bezoeken, dan mag de eerste route dat ook: k start dan bij nul:mijosa schreef: ...
Voor twee routes zijn er dus SOM(k=1 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=1 tot n) n! verschillende mogelijkheden.
...
Daarbij mag het voorkomen dat een route geen enkele knoop bezoekt zolang alle knopen maar wel door een route worden bezocht.
...
SOM(k=0 tot n) (n! / (n-k)!) * (n-k)! = SOM(k=0 tot n) n! = (n+1) * n! = (n+1)!
In tex (quote dit bericht en je ziet de tex-code):
Nu in het algemeen:
Alle knopen worden precies 1 keer bezocht. Als we ze chronologisch achter elkaar plaatsen hebben we dus n! mogelijke bezoekvolgordes.
Elk van die n! mogelijke volgordes moeten we nu nog verdelen over k routes.
Op hoeveel manieren kunnen we een volgorde van n knopen splitsen in k delen?
Hoeveel mogelijkheden zijn er dus in totaal?
Hint: Kijk zo nodig eerst naar een voorbeeld, bv n=6 en k=3:
Voor n=6 wordt knoopvolgorde ABCDEF precies gesplitst in k=3 delen door er 2 scheidingstekens '|' aan toe te voegen.
Vb: AB|C|DEF betekent: route1 = AB, route2=C, route3=DEF
op hoeveel verschillende manieren kunnen we hier die 2 scheidingstekens plaatsen?
Re: Herhaalde partiele permutaties
Beste Arie,
Bedankt voor de hint
Er zijn natuurlijk mogelijk manieren om 2 scheidingstekens te plaatsen in jouw voorbeeld.
In het algemeen zijn er dan zoveel mogelijkheden:
Ik had voor n=4 al een (soort van) kansboom uitgewerkt met als uitkomst 192, en dat komt overeen met:
Bedankt voor de hint
Er zijn natuurlijk mogelijk manieren om 2 scheidingstekens te plaatsen in jouw voorbeeld.
In het algemeen zijn er dan zoveel mogelijkheden:
Ik had voor n=4 al een (soort van) kansboom uitgewerkt met als uitkomst 192, en dat komt overeen met:
Re: Herhaalde partiele permutaties
mijosa: , doet dit je nergens aan denken?
Bedenk dan ook eens hoe je dit antwoord had kunnen vinden zonder te sommeren...
Bedenk dan ook eens hoe je dit antwoord had kunnen vinden zonder te sommeren...
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Herhaalde partiele permutaties
Beste Barto,
Je hebt gelijk, bij nader inzien is dat te schrijven als omdat;
met m=k-1 gelijk is aan:
door het binomium van Newton te gebruiken
Maar,
ik was iets te snel door te stellen dat dit de oplossing van mijn probleem was .
Ik heb in mijn eerste post niet duidelijk genoeg aangegeven dat het doel is unieke routes te vinden.
Daarmee wil ik zeggen dat 1->2->3->4 gelijk is aan 4->3->2->1, want dat is gewoon de omgekeerde route.
Dit probleem lijkt me nog een stuk lastiger omdat voor elke keuze van k en daarmee de
term verschillende soorten dubbele routes oplevert.
Zou iemand mij wellicht iets verder kunnen helpen?
Je hebt gelijk, bij nader inzien is dat te schrijven als omdat;
met m=k-1 gelijk is aan:
door het binomium van Newton te gebruiken
Maar,
ik was iets te snel door te stellen dat dit de oplossing van mijn probleem was .
Ik heb in mijn eerste post niet duidelijk genoeg aangegeven dat het doel is unieke routes te vinden.
Daarmee wil ik zeggen dat 1->2->3->4 gelijk is aan 4->3->2->1, want dat is gewoon de omgekeerde route.
Dit probleem lijkt me nog een stuk lastiger omdat voor elke keuze van k en daarmee de
term verschillende soorten dubbele routes oplevert.
Zou iemand mij wellicht iets verder kunnen helpen?
Re: Herhaalde partiele permutaties
Bedoel je dan dat ook de rondgangmijosa schreef:Maar,
ik was iets te snel door te stellen dat dit de oplossing van mijn probleem was .
Ik heb in mijn eerste post niet duidelijk genoeg aangegeven dat het doel is unieke routes te vinden.
Daarmee wil ik zeggen dat 1->2->3->4 gelijk is aan 4->3->2->1, want dat is gewoon de omgekeerde route.
1,2,3,4 hetzelfde is als 4,1,2,3?
En dat 1,2|3,4 hetzelfde is als 4,3|2,1? (hier zijn er dus 2 routes, gescheiden door '|')
Of hetzelfde als 3,4|1,2 ?
Het hangt er van af welke voorwaarden je precies wilt stellen.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Herhaalde partiele permutaties
Misschien bent u bekend met het traveling salesmen problem TSP?barto schreef: Bedoel je dan dat ook de rondgang
1,2,3,4 hetzelfde is als 4,1,2,3?
En dat 1,2|3,4 hetzelfde is als 4,3|2,1? (hier zijn er dus 2 routes, gescheiden door '|')
Of hetzelfde als 3,4|1,2 ?
Het hangt er van af welke voorwaarden je precies wilt stellen.
Daarin wordt vaak vermeld dat er n! mogelijkheden zijn, maar dat is niet helemaal zo omdat in een symmetrische graaf de tak van i->j dezelfde kosten meebrengen als j->i.
Derhalve is 1,2,3,4 hetzelfde als 4,1,2,3 omdat deze route (getekend op de graaf als cykel) feitelijk dezelfde is.
Mijn probleem is echter wat groter dan het TSP.
Als eerste uitbreiding kan men het zien als een multiple TSP.
Als ik weet hoeveel unieke routes in het mTSP aanwezig zijn, dan zijn er voor mijn probleem x2 zoveel routes.
Misschien dat het nu wat duidelijker is...
Re: Herhaalde partiele permutaties
Ja, dit maakt het duidelijk. Twee configuraties zijn gelijk als hun grafen (die ongeoriënteerd zijn) gelijk zijn.
Dus 1,2|3,4 is niet hetzelfde als 1,2|4,3 omdat de route eigenlijk slechts uit één cyclus bestaat?
Ik kan niet direct een antwoord bedenken, o.a. wegens tijdsgebrek maar ik zal er eens over nadenken.
Dus 1,2|3,4 is niet hetzelfde als 1,2|4,3 omdat de route eigenlijk slechts uit één cyclus bestaat?
Ik kan niet direct een antwoord bedenken, o.a. wegens tijdsgebrek maar ik zal er eens over nadenken.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.
Re: Herhaalde partiele permutaties
Oke mooi, alvast bedankt!
Maar 1-2|3-4 is wel hetzelfde als 1-2|4-3.
Het is idee is als een voertuig de route 3-4 periodiek zou gaan uitvoeren, dan is 3-4 hetzelfde als 4-3.
Periodiek wordt het namelijk 3-4-3-4-3-4-3-4-...-
Maar 1-2|3-4 is wel hetzelfde als 1-2|4-3.
Het is idee is als een voertuig de route 3-4 periodiek zou gaan uitvoeren, dan is 3-4 hetzelfde als 4-3.
Periodiek wordt het namelijk 3-4-3-4-3-4-3-4-...-
Re: Herhaalde partiele permutaties
Beste Barto,
Ik heb zelf nog eens wat onderzoek gedaan en ben op een artikel uit 1975 gekomen waarbij ze bepalen hoeveel 'ELEMENTARY CIRCUITS' en in een gerichte graaf zijn. Ik citeer:
elementary circuits in een complete directe graaf zijn met n knopen.
Graag wil ik weten wat jouw mening hierover is en of dit aansluit bij onze eisen?
Ik heb zelf nog eens wat onderzoek gedaan en ben op een artikel uit 1975 gekomen waarbij ze bepalen hoeveel 'ELEMENTARY CIRCUITS' en in een gerichte graaf zijn. Ik citeer:
Volgens mij is dit waar ik (wij) naar op zoek zijn. Zonder afleiding stellen zij dat er exactA directed graph G (V, E) consists of a nonempty and finite set of vertices
V and a set E of ordered pairs of distinct vertices called edges. There are n vertices
and e edges in G. A path in G is a sequence of vertices Pvu =(v=v1, v2, ..., vk = u)
such that (vi, vi+ 1)e E for 1 <= i < k. A circuit is a path in which the first and last
vertices are identical. A path is elementary if no vertex appears twice. A circuit is
elementary if no vertex but the first and last appears twice. Two elementary
circuits are distinct if one is not a cyclic permutation of the other.
elementary circuits in een complete directe graaf zijn met n knopen.
Graag wil ik weten wat jouw mening hierover is en of dit aansluit bij onze eisen?