Algoritme gevoelsmatige willekeur tbv inkleuren vlakken

[RwD]

Ik heb software dat een grote ruimte vult met rechthoeken die op elkaar aansluiten (geen gaten). Nu moet ik iedere rechthoek willekeurig inkleuren met precies één kleur. In totaal heb ik twee tot, soms wel, 10 kleuren. De inkleuring moet met "een druk op de knop" opnieuw willekeurig gedaan worden, met dus ook een andere verdeling van de kleuren. Tenslotte moet ik iedere inkleuring kunnen herhalen.

Tot zo ver is dit allemaal geen enkel probleem. Ik gebruik een randomfunctie, die ik kan seeden, waar ik x en y aan kan geven. Hiervan krijg ik een willekeurige kleur terug. Om te kunnen reproduceren onthoud ik de seed. Maar omdat ik de kleur kies op basis van een standaard (pseudo-)willekeurgenerator komen er ook klonters voor waarbij 3, 4 of meer aansluitende vakken dezelfde kleur hebben. Die klonters zijn willekeur, maar gevoelsmatig ziet het niet willekeurig uit. Ik ben op zoek om het algoritme te verbeteren, maar ben even vastgelopen.

Wat ik al geprobeerd heb

• Perlin noise heb ik geprobeerd. Maar dit is bedoeld om juist aansluitende vakken locaties aan elkaar te relateren en biedt daarom wel willekeur, maar het wil juist de aansluitende vakken enigszins laten lijken op het vorigegeen verbetering van de situatie.
• Het kleuren van grafen heb ik bekeken. Voor zover ik het kan zien probeert men hiermee sluitende oplossingen te vinden, maar twee vakken naast elkaar mogen best dezelfde kleur hebben. Daarnaast zijn de algoritmes niet erg snel
• Tenslotte heb ik gekeken naar "Low-discrepancy sequences" zoals de Halton en Sobol sequences en de Hammersley set. Deze algoritmes heb ik nog niet kunnen seeden; ze geven altijd hetzelfde resultaat

De vraag
Heeft iemand suggesties welke (snelle) algoritmes een gevoelsmatig egale verdeling kunnen maken? Het principe lijkt me taalonafhankelijk. Dus ieder suggestie in iedere (programmeer-)taal is welkom.

[NMe]

Niet alleen de kleur maar ook het vakje dat gekleurd gaat worden random kiezen uit de nog in te kleuren vakken?

[farlane]

Gevoelsmatig random....ik weet niet. Lijkt me dat als een kleur random kiezen niet random genoeg is je juist iets wilt hebben wat niet (helemaal) random is.

[RobIII]

Gebruik je seed om een initiële kleur en vakje te "kiezen" en gebruik daarna gewoon een deterministisch algoritme dat de volgende vakjes/kleuren bepaalt zodat ze voldoen aan je criteria.

[Janoz]

Ik denk dat het belangrijker is om eerst te bepalen wat je als 'echt random' beschouwt. Als twee naastgelegen vakjes niet dezelfde kleur mogen hebben dan moet je daar iets mee doen. Niet je random functie aanpassen, maar een algoritme gebruiken wat naburige vlakken een andere kleur geeft (en te bepalen of dat uberhaupt wel mogelijk is).

[pedorus]

Wat je zou kunnen doen is de vorige kleur maar de helft van de kans van de anderen geven. Of generieker: bedenken hoe erg de kans van reeds omliggende kleuren moet afnemen.
Vergelijk https://jsfiddle.net/hj9d3fom/1/ met https://jsfiddle.net/hj9d3fom/2/ (2e heeft halve kans voor net gebruikte kleur)

Maar dat soort dingen met gevoel is sowieso lastig, anders moet je even wat voorbeeldplaatjes geven

[RwD]

NMe schreef op maandag 16 januari 2017 @ 23:46:
Niet alleen de kleur maar ook het vakje dat gekleurd gaat worden random kiezen uit de nog in te kleuren vakken?

Het maakt volgens mij niet uit welk vakje ik inkleur als de inkleuring al willekeurig is. Verplaats ik dan niet de klonters?

RobIII schreef op maandag 16 januari 2017 @ 23:55:
Gebruik je seed om een initiële kleur en vakje te "kiezen" en gebruik daarna gewoon een deterministisch algoritme dat de volgende vakjes/kleuren bepaalt zodat ze voldoen aan je criteria.

Dat is min of meer wat de "Low-discrepancy sequences" (is daar Nederlands voor?) doen. Maar dan zou ik moeten kijken of dat acceptabel is. Momenteel kan ik namelijk de inkleuring met een druk op de knop aanpassen. Ik ben bang dat er dan soms pareidolie (bijvoorbeeld een gezicht) ontstaat die we dan niet meer weg kunnen krijgen.

pedorus schreef op dinsdag 17 januari 2017 @ 00:05:
Wat je zou kunnen doen is de vorige kleur maar de helft van de kans van de anderen geven. Of generieker: bedenken hoe erg de kans van reeds omliggende kleuren moet afnemen.
Vergelijk https://jsfiddle.net/hj9d3fom/1/ met https://jsfiddle.net/hj9d3fom/2/ (2e heeft halve kans voor net gebruikte kleur)

Maar dat soort dingen met gevoel is sowieso lastig, anders moet je even wat voorbeeldplaatjes geven

Hier moet ik nog eens goed naar kijken, want je stelt volgens mij voor om telkens de vorige kleur uit te sluiten bij de keuze. Maar ik zie het wel gebeuren. Op zich is dat trouwens niet erg, je voorbeeld illustreert precies het probleem en een mogelijke verbetering/oplossing. Nu heb ik de willekeur compleet anders ingevuld dus ik heb even tijd nodig om dit uit te proberen.

@farlane: klopt!
@Janoz: het is lastig te beschrijven als de voorwaarde "gevoelsmatig" is, maar ik snap je punt. Ik weet wel wat ik wil, maar heb de gevoelsmatige willekeur nog niet formeel geprobeerd te beschrijven. Alleen kan ik me bijna niet voorstellen dat dit nog niet beschreven en mogelijk "opgelost" is.

[Hydra]

Rare suggesties hier:

Tijdens het kleuren kun je gewoon bij iedere random kleur keuze kijken of aanliggende vakken dezelfde kleur hebben. Zo lang er 'buren' met die kleur zijn selecteer je een nieuwe kleur. Als de layout van de vlakken hetzelfde is zul je met dezelfde random seed tot hetzelfde resultaat komen.

In psuedo:

code:

for every uncoloured square:
    do
       color = randomColor()
    while(neighborsHaveColor(color))
    square = color
end

[ Voor 24% gewijzigd door Hydra op 17-01-2017 08:49 ]

[armageddon_2k1]

Misschien ben ik gek, maar ben je effectief niet een landkaart aan het invullen? Je hebt dan genoeg aan 4 kleuren:

Wikipedia: Four color theorem

Daarna is het een kwestie van in 1 vlak beginnen en een random kleur kiezen. Dan naar een aangrenzend vak en random kiezen uit de kleuren die over zijn. Etcetera.

[ Voor 28% gewijzigd door armageddon_2k1 op 17-01-2017 08:55 ]

[Verwijderd]

In welke taal heb je het geprogrammeerd en welke random number generator gebruik je?

Sommige talen hun random-functies blijken niet zo heel random te zijn...

[NMe]

RwD schreef op dinsdag 17 januari 2017 @ 06:59:
[...]
Het maakt volgens mij niet uit welk vakje ik inkleur als de inkleuring al willekeurig is. Verplaats ik dan niet de klonters?

Mogelijk, maar dat is de aard van willekeur. Je zoekt dan eerder een methode om een patroonalgoritme te seeden, min of meer zoals Hydra omschrijft.

[breew]

Kan je niet een maken met "mogelijke kleuren", en een pool met "gebruikte kleuren". Zodra er gekleurd moet worden, kies je random een kleur uit "mogelijke kleuren"; die kleur stop je vervolgens in "gebruikte kleuren".
Alle kleuren die in de pool "gebruikte kleuren" zitten, worden verwijderd uit "mogelijke kleuren" ?

[ Voor 9% gewijzigd door breew op 17-01-2017 14:11 ]

[Morrar]

Wat breew zegt was ook mijn gedachte, maar misschien is dat niet mogelijk als je meer vakken dan kleuren hebt. Daarnaast kun je dan nog steeds kleuren naast elkaar krijgen die heel sterk op elkaar lijken, bijvoorbeeld #FF0000 en #FE0000 om in HTML kleurcodes te spreken

Wat ook zou kunnen is dat je een algritme neemt dat:
- De volledige set van kleuren neemt
- Alle kleuren verwijdert die sterk lijken op het vlak links ervan (als aanwezig)
- Alle kleuren verwijdert die sterk lijken op het vak erboven (als aanwezig)
- Willekeurig een kleur trekt uit de overgebleven set kleuren

Voor het bepalen welke kleuren sterk op elkaar lijken zou je een afstandsmaat kunnen berekenen:
Wikipedia: Color difference

[DJMaze]

Er van uitgaande dat je 8bit gebruikt en niet 10bit:
R = 0 - 255
G = 0 - 255
B = 0 - 255

Pak de kleuren van de aangrenzende rechthoeken en speel met de combinatie ?

[Caelorum]

Verwijderd schreef op dinsdag 17 januari 2017 @ 09:00:
In welke taal heb je het geprogrammeerd en welke random number generator gebruik je?

Sommige talen hun random-functies blijken niet zo heel random te zijn...

Dat maakt hier niet uit. Hij zoekt niet echt random, maar random voor het gevoel. Dat zijn twee heel andere dingen.

[Verwijderd]

Caelorum schreef op dinsdag 17 januari 2017 @ 18:56:
[...]

Dat maakt hier niet uit. Hij zoekt niet echt random, maar random voor het gevoel. Dat zijn twee heel andere dingen.

Geen idee wat het verschil is voor jou dan is, maar (pseudo) random number generatoren programmeren is een kunst apart. En als je een probleem hebt met randomness ligt het 9 op 10 keer aan de gebruikte generator.

[Creepy]

Of aan het gebruik van de generator... Je zou niet de eerste zijn die elke keer de seed zet voor elk nieuw random nummer (bijv op basis van tijd), en dan is het ineens een stuk minder random

@RwD: Wat mij verbaast is dat je een random functie hebt waar je X en Y aan mee geeft. Bedoel je hiermee dat je random functie afhankelijk is van de X en Y coordinaat? Of dat als je dezelfde coordinaat voor een twee keer meegeeft dat je hetzelfde "random" nummer terug krijgt? Dat lijkt mij verkeerd gebruik van een random nummer generator. Kan je uitleggen hoe dat in elkaar steekt?

[Caelorum]

Verwijderd schreef op dinsdag 17 januari 2017 @ 19:50:
[...]
Geen idee wat het verschil is voor jou dan is, maar (pseudo) random number generatoren programmeren is een kunst apart. En als je een probleem hebt met randomness ligt het 9 op 10 keer aan de gebruikte generator.

Simpel, wat mensen aanvoelen als random is anders dan echt random. Als het echt random is kan je zo 5 keer achter elkaar hetzelfde of vrijwel hetzelfde resultaat krijgen. De meeste mensen zullen echter waarschijnlijk bij de 3e keer al wel zeggen dat het niet random is.
Daarnaast geeft hij genoeg hints: gevoelsmatig vet gedrukt en in de laatste alinea zelfs dat hij een egale verdeling van de kleuren wil maken. Dat ga je gewoon niet krijgen met puur random. Dus de taal en welk pseudo-randomgenerator hij gebruikt is een stuk minder relevent, zolang het maar redelijk random is en het door een functie kan worden halen die op basis van die geseede random nummers de resultaten deterministisch bepaalt op zo'n manier dat de vlakken worden bepaalt zonder dat er twee vlakken naast elkaar liggen die dezelfde kleur hebben. Precies wat RobIII overigens al aangaf ^^

[RwD]

@MeHiSt: echte willekeur is niet het probleem, zoals Caelorum o.a. heel goed heeft gezien is het probleem juist dat ik helemaal geen echte willekeur wil, maar iets dat willekeurig aanvoelt.

---

Hydra schreef op dinsdag 17 januari 2017 @ 08:47:
...

code:

for every uncoloured square:
    do
       color = randomColor()
    while(neighborsHaveColor(color))
    square = color
end

Dit zou kunnen werken, maar dan moet ik wel aanpassingen maken zodat van twee aangrenzende vlakken de kleur wel gelijk kan zijn omdat het anders ook niet willekeurig aanvoelt. Ik denk dat de suggestie van Breew dit oplost en het lijkt verder op wat jij aangeeft.

---

armageddon_2k1 schreef op dinsdag 17 januari 2017 @ 08:53:
Misschien ben ik gek, maar ben je effectief niet een landkaart aan het invullen? Je hebt dan genoeg aan 4 kleuren:

Wikipedia: Four color theorem

Daarna is het een kwestie van in 1 vlak beginnen en een random kleur kiezen. Dan naar een aangrenzend vak en random kiezen uit de kleuren die over zijn. Etcetera.

Ik denk dat Hydras code een (incomplete) implementatie is voor onder andere de vierkleurenstelling. Complete implementaties die ik heb gevonden waren wat traag en ik kon het niet echt seeden. Maar ik heb ook niet altijd vier kleuren. Soms minder, soms meer.

---

breew schreef op dinsdag 17 januari 2017 @ 14:11:
Kan je niet een maken met "mogelijke kleuren", en een pool met "gebruikte kleuren". Zodra er gekleurd moet worden, kies je random een kleur uit "mogelijke kleuren"; die kleur stop je vervolgens in "gebruikte kleuren".
Alle kleuren die in de pool "gebruikte kleuren" zitten, worden verwijderd uit "mogelijke kleuren" ?

Goed idee. Zo weet ik te allen tijde zeker dat de distributie van iedere kleur gelijk is, en gezien de manier waarop ik de ruimte vul zou dit mogelijk grote klonters kunnen voorkomen. Ik ben wel benieuwd hoe dit zich uit bij kleine kleurruimtes, bijvoorbeeld drie kleuren A, B en C. Misschien levert het dan wel ABC.ABC.ABC.ABC op omdat er nu een grotere kans komt op afwikkelen kleurruimte in dezelfde volgorde. Maar daar kan ik wel iets op verzinnen.

---

Morrar schreef op dinsdag 17 januari 2017 @ 15:35:
...

Wat ook zou kunnen is dat je een algritme neemt dat:
- De volledige set van kleuren neemt
- Alle kleuren verwijdert die sterk lijken op het vlak links ervan (als aanwezig)
- Alle kleuren verwijdert die sterk lijken op het vak erboven (als aanwezig)
- Willekeurig een kleur trekt uit de overgebleven set kleuren

...

Ik heb een set van vaste kleuren voor iedere ruimte maar vergelijkbare kleuren naast elkaar is vooralsnog geen probleem, zelfs niet als 6 vergelijkbare kleuren samen een klonter opleveren. Het zijn nog steeds verschillende kleuren, en meestal is er duidelijk verschil tussen alle kleuren. Mocht het wel een probleem gaan worden kan ik jouw suggestie wel meenemen, maar dan op basis van HSV (die waardes heb ik al)

@DJMaze: als ik het goed begrijp stel je ongeveer zoiets voor als bovenstaande, maar dan met een andere invalshoek? Het zou dan wel met CIELAB of HSV moeten want RGB niet de beste kleurruimte om de waargenomen afstand tussen twee kleuren te bepalen.

---

Creepy schreef op dinsdag 17 januari 2017 @ 20:23:
...

@RwD: Wat mij verbaast is dat je een random functie hebt waar je X en Y aan mee geeft. Bedoel je hiermee dat je random functie afhankelijk is van de X en Y coordinaat? Of dat als je dezelfde coordinaat voor een twee keer meegeeft dat je hetzelfde "random" nummer terug krijgt? Dat lijkt mij verkeerd gebruik van een random nummer generator. Kan je uitleggen hoe dat in elkaar steekt?

Goed gezien! Ik heb inderdaad voor ieder X en Y coördinaat bij iedere vraag dezelfde willekeurige kleur nodig (totdat ik wil seeden). De reden is dat de ruimte die ik inkleur enorm groot is, zonder herhaling en ik niet alle kleuren van de vlakken kan onthouden. (Daarom keek ik als vervanging meteen naar Perlin noise, hiermee is dat seedbaar en reproduceerbaar in te vullen.) De willekeur komt niet door rechtstreeks een random-functie aan te roepen per vlak, dan zouden de vlakken gaan knipperen van kleur bij iedere iteratie. In plaats daarvan is er een functie die "random genoeg" is en op basis van een X + Y een willekeurige kleur kan teruggeven.

---

Ik ben vandaag niet aan testen toegekomen, maar wat ik wil gaan doen is aan de slag met de voorbeelden van pedorus (kiest uit twee keer de kleurruimte min eenmaal de vorige kleur) en Breew (kiest uit kleurruimte minus vorige kleur tot kleurruimte op is). Want die eerste verkleint de kans op dezelfde kleur maar laat de rest willekeurig. De suggestie van Breew geeft misschien wel het voorspelbaarste gedrag en past toevallig het beste bij de bestaande implementatie.

[Verwijderd]

Caelorum schreef op dinsdag 17 januari 2017 @ 20:40:
[...]

Simpel, wat mensen aanvoelen als random is anders dan echt random. Als het echt random is kan je zo 5 keer achter elkaar hetzelfde of vrijwel hetzelfde resultaat krijgen. De meeste mensen zullen echter waarschijnlijk bij de 3e keer al wel zeggen dat het niet random is.

De kans op 3 keer zelfde getal tussen 1 en 10 is 1 op 1000 bij een uniforme distributie. Zoiets zal dus maar 1 keer per 1000 experimenten voorkomen. An sich blijft het wel random maar tegelijk ook uitzonderlijk.

Uit de TS had ik begrepen dat de clusters elke keer opdoken en in dat geval moet je gaan beginnen denken aan je generator. In het probleem van TS verhoogt de kans om clusters wel wat maar zonder extra info ivm dimensies van de matrix niet na te gaan. Bottom line blijft dat als je last hebt van clusters, je volgende run (met andere seed natuurlijk) deze niet meer mag hebben.

Ik zou gewoon een stukje code schrijven dat de clusters analyseert en als hij er vindt gewoon matrix opnieuw laten vullen. Gaat je veel beter resultaat geven dan determinisme te combineren met randomness

[DJMaze]

RwD schreef op dinsdag 17 januari 2017 @ 22:35:
Ik heb een set van vaste kleuren voor iedere ruimte maar vergelijkbare kleuren naast elkaar is vooralsnog geen probleem, zelfs niet als 6 vergelijkbare kleuren samen een klonter opleveren. Het zijn nog steeds verschillende kleuren, en meestal is er duidelijk verschil tussen alle kleuren. Mocht het wel een probleem gaan worden kan ik jouw suggestie wel meenemen, maar dan op basis van HSV (die waardes heb ik al)

@DJMaze: als ik het goed begrijp stel je ongeveer zoiets voor als bovenstaande, maar dan met een andere invalshoek? Het zou dan wel met CIELAB of HSV moeten want RGB niet de beste kleurruimte om de waargenomen afstand tussen twee kleuren te bepalen.

Inderdaad, maar RGB of HSV maakt eigenlijk niet uit omdat een computer monitor altijd RGB is.
Met HSV kan je makkelijker rekenen, maar heeft ook problemen groen en blauw.
Je bent dan wel beperkt in trappen van 60 (6 kleuren) en sla oranje (30) over.
En met saturation op 50 gebruik je dan een hue van 30, 90, 150, etc.
Heb je wel maar 12 kleuren als ze duidelijk verschillend moeten zijn.

[Hydra]

RwD schreef op dinsdag 17 januari 2017 @ 22:35:
Dit zou kunnen werken, maar dan moet ik wel aanpassingen maken zodat van twee aangrenzende vlakken de kleur wel gelijk kan zijn omdat het anders ook niet willekeurig aanvoelt. Ik denk dat de suggestie van Breew dit oplost en het lijkt verder op wat jij aangeeft.

Dan kun je in plaats van 'geen' aangrenzende vlakken gewoon 'max 1' of whatever nemen. Verder verandert er niks.

Ik heb een set van vaste kleuren voor iedere ruimte maar vergelijkbare kleuren naast elkaar is vooralsnog geen probleem, zelfs niet als 6 vergelijkbare kleuren samen een klonter opleveren. Het zijn nog steeds verschillende kleuren, en meestal is er duidelijk verschil tussen alle kleuren. Mocht het wel een probleem gaan worden kan ik jouw suggestie wel meenemen, maar dan op basis van HSV (die waardes heb ik al)

Reken gewoon met indices. Kleur 1, kleur 2, etc. Aan het eind weet je hoeveel kleuren je nodig hebt en kun je vrij eenvoudig met HSV kleuren er X maken die ver uit elkaar liggen.

DJMaze schreef op woensdag 18 januari 2017 @ 00:54:
Inderdaad, maar RGB of HSV maakt eigenlijk niet uit omdat een computer monitor altijd RGB is.

Het gaat erom dat hij kleuren wil genereren die visueel te onderscheiden zijn. Dat is met HSV makkelijker dan met RGB.

Ik ben een tijd geleden begonnen met het kleuren van een 'landkaart' met een Genetisch Algorithme (https://github.com/nielsutrecht/genetic-graph-coloring) en dat is ook hoe ik daar de kleuren maak.

[ Voor 53% gewijzigd door Hydra op 18-01-2017 08:43 ]

[RwD]

De kleuren die ik heb zijn een gegeven, zo rijg ik bijvoorbeeld blauw, grijs en donkerblauw als vulkleuren. Ik kan wel voorkomen dat vrijwel gelijke kleuren naast elkaar liggen omdat ik de kleur wel ken. Maar dat hoeft nu nog niet.

Wat betreft de suggestie van pedorus; als ik bij het kiezen van een kleur de laatstgekozen kleur 50% kans geef. Wat doe ik dan als mijn kleurruimte iets anders uit ziet? Ik kan namelijk ook [1 x A, 1 x B en 4 x C] hebben als het de bedoeling is dat C ongeveer de helft van de ruimte inneemt (overigens zal C dan altijd clusteren, maar dat is in dit geval ook de bedoeling) Neem ik dan nadat C is gekozen als nieuwe ruimte [2 x A, 2 x B, 4 x C], of [2 x A, 3 x B en 7 x C] of iets anders? In het eerste geval halveer ik de gehele kans op C (lijkt me onjuist omdat ik dan A en B een relatief grote kans geef) in het tweede geval is de kans op C wel iets kleiner, maar wel nog bijna in verhouding. Ik denk zelf dat het tweede geval juist is.

Morgen wil ik gaan uittesten of er een suggestie bij zit die een mooier beeld oplevert. Als het lukt kan ik screenshots maken van het resultaat.

[bomberboy]

RwD schreef op woensdag 18 januari 2017 @ 22:45:
De kleuren die ik heb zijn een gegeven, zo rijg ik bijvoorbeeld blauw, grijs en donkerblauw als vulkleuren. Ik kan wel voorkomen dat vrijwel gelijke kleuren naast elkaar liggen omdat ik de kleur wel ken. Maar dat hoeft nu nog niet.

Ik denk dat het grootste probleem nog steeds is dat je niet goed kan definiëren wat er gewenst is. De oplossingen die Janoz & Hydra vrij snel aangebracht hebben zijn wat mij betreft ook het meest relevant met betrekking tot je huidige probleemomschrijving.

Wat betreft de suggestie van pedorus; als ik bij het kiezen van een kleur de laatstgekozen kleur 50% kans geef. Wat doe ik dan als mijn kleurruimte iets anders uit ziet? Ik kan namelijk ook \[1 x A, 1 x B en 4 x C] hebben als het de bedoeling is dat C ongeveer de helft van de ruimte inneemt (overigens zal C dan altijd clusteren, maar dat is in dit geval ook de bedoeling) Neem ik dan nadat C is gekozen als nieuwe ruimte \[2 x A, 2 x B, 4 x C], of \[2 x A, 3 x B en 7 x C] of iets anders? In het eerste geval halveer ik de gehele kans op C (lijkt me onjuist omdat ik dan A en B een relatief grote kans geef) in het tweede geval is de kans op C wel iets kleiner, maar wel nog bijna in verhouding. Ik denk zelf dat het tweede geval juist is.

Ook hier weer, het is een vorm van experimenteren met kansrekening. Dat werkt in praktijk doorgaans niet, vooral omdat het nog steeds resultaten kan opleveren die niet voldoen aan wat je verwacht maar door de aanpak toch nog steeds kunnen voorkomen. Dat is zoals krasloten kopen met een winstkans van 50% en redeneren dat als je er twee koopt je zeker gewonnen hebt. Het enige resultaat is dat als je dan toch twee maal niet wint je teleurstelling dubbel zo groot is.

Indien je toch een bepaalde sturing wil geven aan je resultaten, bv kleur A komt 2 keer zo veel voor dan kleur B, dan is een mogelijke variant op het algoritme van Hydra om die lijst van te gebruiken kleuren vooraf te bepalen en een random sort te doen op die lijst.

bv:

• Je hebt 8 rechthoeken en 3 kleuren A, B, C.
• Je wil dat kleur A twee keer zo veel voorkomt dan B & C

code:

//Bouw je lijst van 8 rechthoeken:
colors = {A, A, A, A, B, B, C, C};

//doe daarop een random sort:
colors.randomsort();
//resultaat colors = {A, C, A, A, B, B, A, C};

//itereer over alle rechthoeken en wijs kleur toe
for(rectangle in rectangles) {
    color = colors.pop();
    count = 0;
    //colorvalidation bekijkt alle constraints, count is om niet in oneindige loop te komen
    //complexiteit hiervan bepaal je uiteraard zelf
    while(colorvalidation(color) && count++ < colors.size()) {
        colors.push(color); // duw kleur terug naar einde van de lijst (assumptie fifo lijst)
        color = colors.pop(); // neem eerste kleur van de lijst
   }
   rectangle.setcolor(color);
}

Heb je harde bijkomende voorwaarden dat twee rechthoeken echt niet dezelfde aangrenzende kleur mogen hebben, dan neem je de volgende in de rij en pop je die uit de lijst van nog te gebruiken kleuren. Uiteraard rekening houden met de (edge) cases dat er mogelijks geen oplossingen zijn die aan al je constraints voldoen. Maar dat geld voor alle oplossingen in deze thread. Dat zit allemaal in die colorvalidation().

Belangrijk bij dit soort problemen is ook om te definiëren hoe erg het is als het "mis" gaat. Alle oplossingen waarbij je de random functies probeert te beïnvloeden blijven een kans hebben dat het mis gaat. (vaak zeer moeilijk in te schatten hoe groot die kans in realiteit echt is). Is dat misgaan niet erg, experimenteer gerust. Is dat wel erg, dan ben je veel beter af met het type oplossing van Janoz & Hydra en de variant hierboven waarbij je cases hebt die geen oplossing kunnen genereren en dus ook gewoon falen (waarop je dan gepast kan reageren: melding aan gebruiker, andere startcondities gebruiken enz)

[Sissors]

Verwijderd schreef op dinsdag 17 januari 2017 @ 23:11:
[...]


De kans op 3 keer zelfde getal tussen 1 en 10 is 1 op 1000 bij een uniforme distributie. Zoiets zal dus maar 1 keer per 1000 experimenten voorkomen. An sich blijft het wel random maar tegelijk ook uitzonderlijk.

Die kans is 1 op 100 (drie keer een specifieke waarde is 1 op 1000, maar gezien er 10 mogelijkheden voor drie keer hetzelde getal zijn, is de kans 1 op 100).

Nou laten we stellen dat TS 20 plaatsen heeft waar potentieel een cluster kan ontstaan, dan is de kans 20% dat het gebeurd. Heeft hij slechts 8 kleuren dan is die kans al meer dan 50%. Oftewel beetje afhankelijk van het formaat en aantal kleuren zal dit vaak voorkomen. En hoewel een random generator soms slecht kan zijn, moet hij wel heel erg slecht zijn als hij dit veroorzaakt. Immers we hebben het hier niet over encryptie ofzo waar veel hogere eisen zijn aan randomness.

Bottom line blijft dat als je last hebt van clusters, je volgende run (met andere seed natuurlijk) deze niet meer mag hebben.

Die specifieke zeer waarschijnlijk niet nee, maar een ander weer wel.

Ik zou gewoon een stukje code schrijven dat de clusters analyseert en als hij er vindt gewoon matrix opnieuw laten vullen. Gaat je veel beter resultaat geven dan determinisme te combineren met randomness

Dat is overigens imo ook een prima idee. Even ervan uitgaande dat we niet een verdeling hebben dat het bijna een gegeven is dat er een cluster is, en dat hij 5000 runs moet doen voor hij er eentje heeft die aan de eisen voldoet.

[Verwijderd]

Sissors schreef op donderdag 19 januari 2017 @ 09:07:
[...]

Die kans is 1 op 100 (drie keer een specifieke waarde is 1 op 1000, maar gezien er 10 mogelijkheden voor drie keer hetzelde getal zijn, is de kans 1 op 100).

dom van me, begreep al niet waarom ik teveel clusters had bij een 10x10 veld.

[armageddon_2k1]

RwD schreef op dinsdag 17 januari 2017 @ 22:35:
Ik denk dat Hydras code een (incomplete) implementatie is voor onder andere de vierkleurenstelling. Complete implementaties die ik heb gevonden waren wat traag en ik kon het niet echt seeden. Maar ik heb ook niet altijd vier kleuren. Soms minder, soms meer.

Als je minder hebt, wordt het sowieso een probleem, want het Four-Color-Theorem werkt ook de andere kant op. Je hebt er minstens 4 nodig om niet 2 aangrenzende zelfde te krijgen.

[RwD]

@bomberboy Je hebt gelijk; ik kan niet goed specificeren wat de bedoeling is. Maar de vraagstelling is een gelijkmatigere distributie van kleuren, maar niet zover dat het niet willekeurig uitziet. Hoe formaliseer je dat? Wat je denk ik niet hebt begrepen is dat ik iedere inkleuring moet kunnen herhalen gegeven een seed. De voorstellen die je doet werken daarom niet voor de vraag en herhalen bovendien wat breew voorstelde. Met wat aanpassingen kan ik jullie voorstel wel gebruiken; ik schud de kleuren niet, maar gebruik mijn pseudorandomfunctie om een kleur uit te kiezen. Daarna haal ik die kleur uit de kleurruimte tot de kleurruimte leeg is. Hierna plaats ik alle kleuren weer in dezelfde volgorde in de kleurruimte. Het verschil met wat ik nu doe is dat ik voorheen de kleurruimte niet kleiner maakte.

@pedorus Ik heb vandaag geëxperimenteerd met jouw suggestie in mijn applicatie, en doordat ik de kans op die manier beïnvloed ontstaan er strepen in x of y richting (afhankelijk welke je eerst doorloopt). Nu doorloop ik de ruimte iets anders maar ook dan zag ik strepen. Ik heb het effect overdreven in deze fiddle zodat het goed (horizontaal) zichtbaar is: https://jsfiddle.net/hj9d3fom/6/

Rest me de oplossing van breew proberen, met de hierboven genoemde aanpassingen.

[RwD]

Ik heb nu geprobeerd om een kleurlijst bij te houden zoals breew opperde. De totale verdeling van tegels is nu exact zoals gevraagd, maar ook hier treden strepen op in horizontale richting (want ik werk van boven naar onder, van links naar rechts). Ik kon dit enigszins beïnvloeden door de kleurruimte 3 keer te vullen met iedere kleur, maar ook dan was enige streepvorming herkenbaar.

Beide oplossingen werken helaas niet zoals gewenst.

Ik heb niet de mogelijkheid om van het vlak dat ik in wil kleuren de buren op te vragen, dus algoritmes die op basis van de buren werken vallen überhaupt af.

Mocht iemand nog een pseudorandomfunctie kennen die een gelijkmatige verdeling oplevert houd ik me aanbevolen.

[RobIII]

Het hele probleem is dat je nog steeds een RNG gebruikt om kleuren te kiezen waar je dat helemaal niet wil. Als er eenmaal een vakje is gekleurd (prima, random vakje, random kleur) zul je vanaf dat punt een deterministisch algoritme moeten gebruiken om te voorkomen dat er zich situaties voordoen die ongewenst zijn: op elkaar lijkende kleuren aangrenzend van elkaar. Je wil juist specifiek een kleur kiezen die op een bepaalde plek past. In het allersimpelste geval maak je gewoon een matrix of kleur X naast Y past en kies je telkens voor een gegeven vakje uit die "selectie" van kleuren uit die matrix (al dan niet met een RNG; persoonlijk zou ik gewoon 1 voor 1 de mogelijke kleuren gebruiken uit die matrix). Mocht je op een punt komen waar je niet meer uit komt / jezelf "in een hoekje geschilderd hebt", dan kun je een stukje backtracking doen en een (paar) vakje(s) terug gaan en een andere kleur kiezen. Dit algoritme kun je naar gelang je wensen bijstellen maar je wil een RNG, in principe, zo weinig mogelijk laten bepalen wat de volgende kleur wordt (tenzij aan banden gelegd en het om het even is of het kleur A, B of C is voor een gegeven vakje). En uiteraard wil je dan inderdaad ook een deterministische RNG zodat je op basis van de seed je resultaten kunt reproduceren.

Wat je allemaal moeilijk zit te doen met "gelijkmatige distributie" van je RNG enzo ontgaat me helemaal; dat is totaal irrelevant in een opzet zoals ik hierboven beschrijf. De resultaten zien er nét zo 'random' uit (mits goed geïmplementeerd). De RNG heeft, behalve hooguit het eerste vakje (wélk en diens kleur) amper tot geen invloed op het geheel.

[ Voor 31% gewijzigd door RobIII op 20-01-2017 11:03 ]

[bomberboy]

RwD schreef op donderdag 19 januari 2017 @ 23:00:
@bomberboy Je hebt gelijk; ik kan niet goed specificeren wat de bedoeling is. Maar de vraagstelling is een gelijkmatigere distributie van kleuren, maar niet zover dat het niet willekeurig uitziet. Hoe formaliseer je dat?

Dat is aan jou. Maar zoals je het hier omschrijft is het heel subjectief. Het subjectieve deel moet je er uithalen. Anders vind je nooit een oplossing warvan je kan zeggen dat ze wel/niet correct is.

Wat je denk ik niet hebt begrepen is dat ik iedere inkleuring moet kunnen herhalen gegeven een seed.

Indien je die randomsort uitvoert met een RNG met bepaalde seed. Waar in het algoritme denk je dat het dan niet deterministisch dezelfde oplossing zal opleveren?

De voorstellen die je doet werken daarom niet voor de vraag en herhalen bovendien wat breew voorstelde. Met wat aanpassingen kan ik jullie voorstel wel gebruiken; ik schud de kleuren niet, maar gebruik mijn pseudorandomfunctie om een kleur uit te kiezen. Daarna haal ik die kleur uit de kleurruimte tot de kleurruimte leeg is. Hierna plaats ik alle kleuren weer in dezelfde volgorde in de kleurruimte. Het verschil met wat ik nu doe is dat ik voorheen de kleurruimte niet kleiner maakte.

Hier lees jij denk ik iets heel anders dan ikzelf in wat breew voorstelde

@pedorus Ik heb vandaag geëxperimenteerd met jouw suggestie in mijn applicatie, en doordat ik de kans op die manier beïnvloed ontstaan er strepen in x of y richting (afhankelijk welke je eerst doorloopt). Nu doorloop ik de ruimte iets anders maar ook dan zag ik strepen. Ik heb het effect overdreven in deze fiddle zodat het goed (horizontaal) zichtbaar is: https://jsfiddle.net/hj9d3fom/6/

Nogmaals, zonder dat je regeltjes opstelt van wat ok is en wat niet ga je nooit tot een goede oplossing komen.

Ik heb niet de mogelijkheid om van het vlak dat ik in wil kleuren de buren op te vragen, dus algoritmes die op basis van de buren werken vallen überhaupt af.

Zorg er dan voor dat je die functie wel hebt ipv in het ijle een oplossing proberen te vinden?

Zoals RobIII ook aangeeft, je concentreert je op de verkeerde problemen

[ElCondor]

Is dit niet een zelfde probleem waar Apple me zat toen mensen klaagden over de random playlist functie van de iPod. Er werd geklaagd dat bepaalse nummers soms achter elkaar, meerdere keren, herhaald werden.
Apple had wel degelijk een RNG geïmplementeerd met clustervorming tot gevolg.

Ze hebben toen het algoritme wel aangepast om het voor het gevoel random te maken zonder dat het écht random is.

Ionica Smeets heeft er ooit een collumn over geschreven in de VK.

Zowieso wordt er op het internet veel over geschreven:
https://www.cnet.com/news/itunes-just-how-random-is-random/

[ Voor 11% gewijzigd door ElCondor op 24-01-2017 13:43 ]

[RwD]

@RobIII ervan uitgaande dat ik mijn vak in kan kleuren in een volgorde x naar y en weet wie de buren zijn zou dat kunnen. Ik heb de wijzigingen in de willekeur getest met een ruimte waarin de tekenvolgorde x, y is omdat dit het meeste voorkomt en lijkt op wat iedereen verwacht als ze antwoord geven in deze thread. Maar ik heb ook een aantal ruimtes waarin ik per x en y een cluster van misschien wel 30 vlakken inkleur. En ik weet niet op een manier die makkelijk in het geheugen past en snel is wat de buurman van vlak (612, 97332) is. Hoe dan ook wil ik toch gaan proberen om deterministisch in te gaan kleuren, al weet ik nog niet hoe.

Al het experimenteren is niet voor niets geweest, er komen mogelijk nieuwe features uit voort waarmee de eindgebruiker misschien zelf de randomfunctie kan gaan kiezen wat nog veel meer mogelijkheden oplevert dan ik bij de originele vraag had kunnen bedenken. Daardoor zouden de eisen die ik had kunnen vervallen en is iedere manier van inkleuren interessant omdat het een totaal ander beeld op kan leveren.

[armageddon_2k1]

Heb je ook al eens gekeken naar "Metaheuristiek"? Met andere woorden: Je specificeert een criterium dat moeilijk deterministisch te vatten is en gebruikt een zoekalgoritme (evolutionair, of whatever) om allemaal mogelijke oplossingen te genereren voor je? Het genereren moet vrij snel gaan bij je, dus de 'fitness' evaluatie ook. Best een leuke uitdaging me dunkt.

Wat leesvoer: https://cs.gmu.edu/~sean/book/metaheuristics/ [Gratis boek! Erg praktisch :)]

[RobIII]

RwD schreef op zaterdag 21 januari 2017 @ 05:52:
Maar ik heb ook een aantal ruimtes waarin ik per x en y een cluster van misschien wel 30 vlakken inkleur. En ik weet niet op een manier die makkelijk in het geheugen past en snel is wat de buurman van vlak (612, 97332) is.

Ik zal 't simpel maken: Je zult of:

[list]
• Iets moeten weten over de vakjes en diens buren
• de kleurruimte drastisch groter moeten maken


om clustering te (kunnen) voorkomen. Je kunt met een (drastisch) grotere kleurruimte de kans (drastisch) naar beneden brengen dat er 2 vakjes naast elkaar dezelfde kleur krijgen; als je keuze hebt uit het hele 24 bit spectrum (16.8 miljoen kleuren) is de kans klein (niet nul) dat 2 vakjes naast elkaar dezelfde kleur hebben. Maar dan nog heb je kans dat 2 vakjes naast elkaar een op elkaar lijkende kleur hebben. En je geeft zelf aan dat je kleurruimte (behoorlijk) beperkt is (logisch ook wel, zodoende kun je kiezen uit contrasterende kleuren en een samenhangend palet). En dan kom je vanzelf uit bij het andere punt: je zult iets moeten weten over de plaatsing van de vakjes en diens buren.

En om het dan nog maar eens te herhalen: je kunt dan wel een RNG gebruiken om een kleur per vakje te kiezen, diens buren te bekijken, te concluderen dat die kleur niet 'geschikt' is en weer een andere kleur gebruiken maar dat gaat nooit efficiënt werken en kan in bepaalde gevallen zelfs een hele poos duren voordat je 'toevallig' de juiste kleur kiest voor dat vakje omdat die net wat onhandige buurkleuren heeft. En dus is de enige efficiënte weg een deterministisch algoritme. En dat kan prima 'gevoelsmatige willekeur' opleveren.

[MSalters]

armageddon_2k1 schreef op donderdag 19 januari 2017 @ 17:53:
[...]
Als je minder hebt, wordt het sowieso een probleem, want het Four-Color-Theorem werkt ook de andere kant op. Je hebt er minstens 4 nodig om niet 2 aangrenzende zelfde te krijgen.

Dat geldt voor planair ingebedde grafen (landkaarten). Met andere woorden, 4CT betekent dat er tenminste 1 landkaart is die de desbetreffende eigenschap heeft. Echter, in dit geval is het domein significant kleiner omdat de kaart uitsluitend rechthoeken bevat. Dat betekent dus dat je 4CT niet meer kunt inverteren; het is niet gegeven dat het tegenvoorbeeld van 4CT in deze subset valt.

Praktisch gesproken heb je het simpele voorbeeld van een centrale cirkel met 3 taartpunten eromheen; 4 delen en toch al 4 kleuren noodzakelijk omdat alles aan elkaar grenst. Maar met 4 rechthoeken zijn 3 kleuren voldoende.

[Bewijs]
Als eerste moeten we een onderscheid maken tussen een landkaart met 4 rechthoekige landen en een meer in het midden (2 kleuren voldoende) en landkaarten zonder meer. In dat laatste geval kunnen we 3-landen punten hebben, maar dat zijn punten waar een Oost-West grens eindigt op een Noord-Zuid grens of andersom. (Elke grens tussen twee rechthoekige landen is OW of NZ). We kunnen nu maximaal 2 3-landen punten hebben: het stuk grens dat de twee verbindt staat haaks op beide andere grenzen, en die andere grenzen lopen _dus_ parallel en kunnen geen derde 3-landen punt vormen.

Overigens kun je met 6 rechthoeken al aantonen dat je nog steeds 4 kleuren nodig hebt: kwestie van 5 rechthoeken rondom een centraal vierkant, dan heb je ook 5 3-landen punten rondom het vierkant.

[ Voor 30% gewijzigd door MSalters op 23-01-2017 22:43 ]

[bwerg]

RwD schreef op vrijdag 20 januari 2017 @ 09:55:
Mocht iemand nog een pseudorandomfunctie kennen die een gelijkmatige verdeling oplevert houd ik me aanbevolen.

Ik zeg een beetje hetzelfde als RobIII, maar toch even voor de duidelijkheid: wat je 'gelijkmatige verdeling' noemt, heeft juist niets te maken met een onafhankelijke kansverdeling of uniforme kansverdeling, of eigenschappen die je in randomness doorgaans zoekt. Richt je daarom op iets wat gewoon werkt in plaats van dat je het in dat soort eigenschappen probeert te vangen.

De enige mogelijke manier die ik kan bedenken om wél onafhankelijk te kiezen (zonder iets van de buren te weten), is om de kansruimte niet uniform te maken, maar juist te laten 'golven', zodanig dat als je op positie x=10 iets zoekt, je een grote kans hebt op kleur A, en op positie x=42, een grotere kans op kleur B, waarbij de vakjes mooi op die plekken terecht komen. Dan moet je dus wel de afstanden tussen vakken kunnen inschatten, en moet je een pseudorandom-functie maken die op die afstanden veel verschillen in kansverdeling. Maar dat lijkt me een veel moeilijkere aanpak dan het hierboven genoemde, tenzij het bekijken van buren echt héél moeilijk is.

[RwD]

Het weten van de kleur van de buren is niet mogelijk want er is van geen vlak met zekerheid bekend wat de positie is tot ze getekend worden. En van ieder vlak de positie onthouden in een virtueel oneindige ruimte met beperkt geheugen is niet te doen.

Mijn oorspronkelijke vraag kan misschien niet beantwoord worden omdat ik hoopte dat dit "bekend probleem" een praktische implementatie zou hebben. Dus een random generator die over x en y en gelijkmatige verdeling oplevert. Uit alle antwoorden lijkt het zo te zijn dat er nog geen algemene oplossing voor bestaat.

Ik ga verder aan de slag zoals o.a. RobIII en bwerg suggereren. Mocht ik onverhoopt alsnog op een bestaande algemene oplossing stuiten zal ik dat hier aanvullen.