binær kombinatorikk uten speilvendte løsninger

[Gravkrok]

Jeg prøver å lære meg å programmere på fritiden, men klarer bare ikke å finne ut av dette.

Hvor mange unike utfall er det for en sekvens med lengde M. (Med unike utfall menes det at sekvensen 100 blir sett på som den samme som 001, altså at den speilvendte løsningen ikke telles.)

For en lengde på 3 blir det altså 000, 100, 010, 101, 111, 110 (6 muligheter)

Har løst opp til lengde 6 for hånd. (4,5,6 gav 10,18,36)

Har i tillegg lagt merke til at sekvensen har noen likheter med Fibonacci tallene (uten at det hjalp meg mer)

[tiago]

For en programmerings løsning: Generer alle mulige kombinasjoner. For vær kombinasjon må en må se på om tallet er odde lengde eller ikke. Hvis odde ser en på om venstre side og høyre side er lik, hvis par deler man lengden i to og ser om begge delene er like. Disse tilfellene har ingen speilvendt løsning, så en legger til 1 hvis delene er like. Deretter sjekker en om tallet er et polidrom (lik hvis en leser fra vesntre som fra høyre). Hvis polidrom øker du counteren for antall polidrom en har med en, ellers legger man til en i antallet for ikke-speilvendt løsning.
Når en er ferdig legger en til antall polidrom / 2 til antall ikke-speilvendte løsninger, som vil være partall pga polidrom uten at v.s og h.s er lik.

Hvis du ønsker matematisk løsning må du bruke inklusjon-ekslusjons prinsippet
https://en.wikipedia.org/wiki/Inclusion ... _principle for å lage en formel.
Om du leter finner du sikkert en formel som regner ut ditt problem raskt, slik at du selv ikke trenger å utlede formelen.

[tiago]

obs.. ser at polidrom ikke blir riktig. Bytt ut speilvendt sjekk så har du det...

[Gjest]

Ok, hvis du skal ha speilvendt på den måte du beskriver holder det å du huske tidligere løsninger via hasmap, og se om det å lese fra høyre gir en løsning en allerede har.

Det blir nok løsningen.

[tiago]

Hvis du ikke får bruke hashmap, er jeg ganske sikker på at det går i retning av:

https://en.wikipedia.org/wiki/Burnside%27s_lemma, hvor en må finne antall permutasjoner på en måte slik at tallet ikke er mirrored til en annen.

Kansje du også kan bruke polidrom våset til å booste opp prosessen.

[Aleks855]

Tror ikke du har nevnt det spesifikt, men skal alle strengene være binære?

Og hvilket programmeringsspråk bruker du?

[tiago]

Observasjon:

Går an å dele stringen i 2 deler, og bitflippe begge deler. Hvis odde blir midterste uberørt.
Hvis resultatet av bitswitch er det samme som en hadde bakvendt legger en ikke til noe. Dvs en legger til 1 unik løsning, men så fjerner man den andre løsningen fra total telle pott. Hvis det ikke er tilfellet legger man til 1.


000 1 111 <-> bitflipOp på begge sider 111 1 000
101 0 010 <-> bitfilipOp på begge sider 010 0 101
1 0 0 <-> bitfilipOp på begge sider 0 0 1
1 1 0 1 0 0 <-> bitfilipOp på begge deler 0 0 1 0 1 1

Ingen spelvendt løsning når:

1 1 1 <-> 0 1 0
0 1 0 <-> 1 0 1

Tror dette er veien å gå

[tiago]

En må dog fortsatt ha en metode for å telle + 1 neste gang en møter tilsvarende ting, og ikke legge til 0.

[tiago]

ok, hvis en bare ser på halve stringen så legger man til 1 hvis en har endret på høyre del av stringen, og 0 hvis på venstre siden. Dvs at en bare lar en av dem telle bidraget. Hvis ingenting skjer så legger en til 1 som vanlig.

Altså er algoritmen

for all permuttion x in X
If x in høyre del
//Legger til unsett om den har bitflip som er revers av x.
pot := pot + 1;
else if venstre del
if bitflip sjekk gir utslag
plot := plot + 1;
else
pot := pot + 0;
//F.eks hvis odde lengde og en endrer midterste.
else
pot := pot + 1;
end
end


0 0 1 0 1 0 1

[tiago]

Mer riktig nå:

for all permuttion x in X
If in høyre del
//Legger til unsett om den har bitflip som er revers av x.
pot := pot + 1;
else if venstre del
if bitflip sjekk gir utslag
plot := plot + 0;
else
pot := pot + 1;
//F.eks hvis odde lengde og en endrer midterste.
else
pot := pot + 1;
end
end

[Gravkrok]

Bruker Phyton, og viser ser at det finnes en Lozanić's triangle som passer til oppgaven.

2**(n - 1)+2**(math.floor((n + 1)/2) - 1) her er formelen som funker.

Men får unøyaktigheter med høyere tall...

[tiago]

Min algortime ser ut til å være vås. Kan uansett løses med burnside lemma. Har aldri hørt om andre måter å løse det på uansett.

Det er ingen kobling mellom problemet og fibonacci.