Într -o postare anterioară, ne -am uitat la algoritmul lui Dyson (Dyson 1946) pentru rezolvarea Monede în
Problema cântăririlor:
Cea mai faimoasă versiune a acestei probleme este rezolvarea a 12 monede în 3 cântăriri; Acesta este un exemplu al cazului special în care care este numărul maxim de monede care pot fi rezolvate în
cântăriri. Versiunea algoritmului pe care l -am arătat în postarea anterioară a rezolvat exact acest caz. În această postare, vom ajusta acel algoritm la cazul mai general unde
.
Schița algoritmului de caz special
Probabil doriți să revizuiți postarea anterioară înainte de a trece la aceasta, dar voi schița rapid algoritmul de caz special aici.
- În primul rând, numărați monedele din
1:M
. Apoi, alocați fiecărei monede o etichetă care corespunde fie reprezentării trinale semnate a numărului său, fie negației acestui număr, în funcție de reprezentarea se rotește „înainte” (definită pentru a însemna că prima schimbare a cifrelor crește cu 1, modulul 3) . - Apoi, determinați un „program de cântărire”: ce monedă merge acolo pentru fiecare cântărire. Poziția fiecărei monede pe
cântărirea este determinată de
cifra (începând din stânga):
înseamnă tigaia din stânga,
înseamnă tigaia potrivită și
înseamnă masa.
- În mod similar, înregistrăm rezultatul fiecărui cântărire prin care tigaia este mai grea (dacă există):
înseamnă că tigaia din stânga este mai grea,
înseamnă că tigaia potrivită este mai grea,
înseamnă că scara este echilibrată.
Așa cum am arătat în ultima postare, dacă Moneda este un dud greu, va descrie propria sa etichetă în semnul semnat, ca
. Un dud ușor va scrie negația etichetei.
Puteți recupera reprezentarea zecimală a rezultatului final, ca
Atunci locația dudului este iar dudul este greu dacă
se rotește înainte și este ușor dacă
se rotește înapoi. Dacă nu există dud, atunci
.
Cazul general
Algoritmul de caz general funcționează practic la fel, dar acum etichetele de monedă nu corespund direct cu numerele de monedă (care sunt încă 1:M
) În schimb, sunt repartizați de la grupuri de „tripluri de cântărire” sau grupuri ciclice, într -un mod care menține numărul de scară egală în prima rundă.
Putem folosi apoi același program de cântărire ca în Carcasă, cu un pic de contabilitate suplimentară pentru a menține ca scara să fie egală în fiecare rundă. Ca și înainte, scala va descrie eticheta monedei dud dacă dudul este greu sau negația etichetei, dacă dudul este ușor.
Pentru a face acest concret, vom folosi exemplul de Cântările, dar acum vrem să rezolvăm mai puțin de 12 monede. Puteți găsi codul pe care îl sun în acest exemplu aici.
Să ne uităm din nou la reprezentările înainte pentru 12 monede.
Afișați codul
source("dyson_signed_general.R") library(poorman) # dplyr will work here, too nrounds = 3 Fmat = get_forward_representation(nrounds) Fmat
(,1) (,2) (,3) (1,) 0 0 1 (2,) 0 1 -1 (3,) 0 1 0 (4,) 0 1 1 (5,) 1 -1 -1 (6,) 1 -1 0 (7,) 1 -1 1 (8,) -1 0 1 (9,) -1 0 0 (10,) -1 0 -1 (11,) 1 1 -1 (12,) -1 -1 0
În cele de mai sus, numerele de rând ale matricei sunt numerele de monede. Când rezolvăm 12 monede, reprezentările înainte ale numerelor de monede dau etichetele pentru fiecare monedă.
1. Creați „cântărirea tripletelor”.
Când dorim să rezolvăm mai puțin de 12 monede, numărul de monedă și reprezentările forward nu mai corespund direct. Trebuie să atribuim etichetele după cum urmează.
Vom începe cu eticheta (0 0 1)
și creșteți fiecare cifră cu 1 modulul 3, pentru a obține o nouă etichetă înainte, (1 1 -1)
. Vom numi asta a Schimbare ciclică. Apoi vom lua noua etichetă și o vom schimba din nou pentru a face un triplet.
coin 1: label (0 0 1) (1) coin 2: label (1 1 -1) (11) coin 3: label (-1 -1 0) (12) # -12, actually, but this is the forward representation
Acesta este primul grup (sau triplet).
Acum obțineți următoarea etichetă neasignată ((0 1 -1) = 2
), și faceți o altă triplă și așa mai departe, până când toate etichetele sunt alocate unui grup. Acest lucru rezultă în grupuri. Pentru acest exemplu, adică 4 grupuri. Vă puteți gândi la fiecare grup ca la o „triplă cântărire”, deoarece fiecare cântărire a celor trei monede împreună are o monedă la stânga, una pe dreapta și una pe masă, la fiecare rundă.
Iată toate posibilele etichete de monede, grupurile lor și cifrele reprezentărilor înainte.
Afișați codul
gps = create_cyclic_groups(nrounds) M_max = (3^nrounds - 3) / 2 gpmap = data.frame(group = gps, coin_label = 1:M_max) gpmap = cbind(gpmap, data.frame(Fmat)) arrange(gpmap, group, coin_label) |> knitr::kable()
1 | 1 | 0 | 0 | 1 |
1 | 11 | 1 | 1 | -1 |
1 | 12 | -1 | -1 | 0 |
2 | 2 | 0 | 1 | -1 |
2 | 6 | 1 | -1 | 0 |
2 | 8 | -1 | 0 | 1 |
3 | 3 | 0 | 1 | 0 |
3 | 7 | 1 | -1 | 1 |
3 | 10 | -1 | 0 | -1 |
4 | 4 | 0 | 1 | 1 |
4 | 5 | 1 | -1 | -1 |
4 | 9 | -1 | 0 | 0 |
Rețineți că grupurile pot fi precompilate, dacă știți .
2. Alocați etichete monedelor
Acum, dacă ai monede,
în loc să le atribuiți etichete secvențiale, le atribuiți etichete de la fiecare grup, în ordine. Primele 3 monede primesc etichete de la primul grup, următorul 3 din al doilea grup, etc. Vei avea
Monede rămase. Dacă
alocați ultimele două monede membrilor următorului grup care încep cu cifrele
-1
şi 1
; dacă apoi alocați ultima monedă membrului următorului grup care începe
0
.
Să încercăm câteva exemple. Primul grup are etichetele (1, 11, 12)
iar al doilea grup are etichetele (2, 6, 8)
. Să presupunem că avem 5 monede. Apoi am atribui primele trei monede etichetele 1, 11, 12, iar ultimele două monede etichetele 6 ((1 -1 0)
) și 8 ((-1 0 1)
)
coin 1: label (0 0 1) (1) coin 2: label (1 1 -1) (11) coin 3: label (-1 -1 0) (12) coin 4: label (1 -1 0) (6) coin 5: label (-1 0 1) (8)
Dacă avem 4 monede, am atribui primele trei monede etichetele 1, 11, 12, iar ultima monedă de la eticheta 2 ((0 1 -1)
)
coin 1: label (0 0 1) (1) coin 2: label (1 1 -1) (11) coin 3: label (-1 -1 0) (12) coin 4: label (0 1 -1) (2)
3. cântăriți monedele conform programului de cântărire.
Programul de cântărire este același ca înainte, dar acum folosim doar unele dintre etichete. Fiecare monedă este plasată pe scară în funcție de cifrele etichetei sale. Iată programul de cântărire pentru prima cântărire:
Afișați codul
Cset = compileC(Fmat) knitr::kable(Cset((1)))
8 | 1 | 5 |
9 | 2 | 6 |
10 | 3 | 7 |
12 | 4 | 11 |
Deci, prima cântărire a cinci monede este următoarea:
coin1 (1): table coin2 (11): right coin3 (12): left coin4 (6): right coin5 (8): left ( {coin3, coin5} | {coin2, coin4} ) ------------------------------------ coin1
De data aceasta, pe lângă faptul că urmărește rezultatul cântăririi De asemenea, trebuie să urmărește monedele pe care le știm că sunt bune, pe baza rezultatului cântăririi. Știm asta
- Dacă scala este echilibrată, atunci toate monedele de pe scară sunt bune (dudul este pe tabel) și
- Dacă scara nu este echilibrată, atunci toate monedele de pe masă sunt bune (dudul este pe scară).
Să presupunem că scara se înclină corect (a(1) = 1
) Atunci știm asta coin1
este bun. Acum, până la a doua greutate:
Afișați codul
knitr::kable(Cset((2)))
5 | 1 | 2 |
6 | 8 | 3 |
7 | 9 | 4 |
12 | 10 | 11 |
coin1 (1, good): table coin2 (11): right coin3 (12): left coin4 (6): left coin5 (8): table ({coin3, coin 4} | {coin2} ) ------------------------------ coin1, coin5
! Acum, numărul de scară nu este egal. Dar știm asta coin1
este bun, astfel încât să -l putem pune în tigaia potrivită pentru a egaliza numărul de monede fără a afecta rezultatul.
({coin3, coin 4} | {coin2, coin1} ) ------------------------------ coin5
Uneori, numărul de scară nu este egal, dar niciuna dintre monedele de pe masă nu a fost marcată bine. În acest caz, găsiți o monedă bună în tigaie cu mai multe monede și puneți -o pe masă.
Pentru a continua exemplul, să spunem că scara se înclină din nou corect (a(2) = 1
) Acum știm asta coin5
este bun. Pe cântărirea a trei.
Afișați codul
knitr::kable(Cset((3)))
2 | 3 | 1 |
5 | 6 | 4 |
10 | 9 | 7 |
11 | 12 | 8 |
coin1 (1, good): right coin2 (11): left coin3 (12): table coin4 (6): table coin5 (8, good): right ({coin2} | {coin1, coin5}) --------------------------- coin3, coin4 Move either of coin1 or coin5 to the table. ( {coin2} | {coin1} ) ----------------------- coin3, coin4, coin5
Acum, de data aceasta, scala se înclină (a(3) = -1
) Avem a = (1 1 -1)
ceea ce înseamnă . Eticheta 11 corespunde la
coin2
și a
se rotește înainte, deci dudul este coin2
și este greu.
Să confirmăm asta cu cod. Ca și înainte, funcția find_dud
Returnează o valoare D
astfel încât abs(D)
dă indexul dudului și sign(D)
Oferă greutatea relativă a dudului: negativ înseamnă că dudul este ușor, iar pozitiv înseamnă că dudul este greu.
Afișați codul
nrounds = 3 ncoins = 5 coins = numeric(ncoins) + 1 # good coins weigh 1 unit # precompilation computes both # the weighing schedule and the label groups precompiled = precompile(nrounds) # make coin 2 a heavy dud coins(2) = 1.5 find_dud(coins, precompiled)
Vom încerca 10 monede.
Afișați codul
ncoins = 10 coins = numeric(ncoins) + 1 # no dud case find_dud(coins, precompiled)
Afișați codul
# 7, light coins(7) = 0.5 find_dud(coins, precompiled)
Afișați codul
# confirm all possible cases work for(icoin in 1:ncoins) { for (direction in c(-1, 1)) { coins = numeric(ncoins) + 1 coins(icoin) = 1 + 0.5 * direction actual = icoin * direction result = find_dud(coins, precompiled) stopifnot(actual == result) } }
Acest lucru generalizează algoritmul lui Dyson. Nu este la fel de drăguț ca versiunea specială de caz, dar funcționează.
Nina Zumel este un om de știință de date cu sediul în San Francisco, cu peste 20 de ani de experiență în învățarea automată, statistici și analize. Ea este co-fondatorul firmei de consultanță în domeniul științei de date Win-Vector LLC și (cu John Mount) coautorul științei datelor practice cu R, aflat acum în a doua ediție. ## Referințe
Dyson, Freeman J. 1946. „Notă 1931 – Problema bănuilor.” Gazeta matematică 30 (281): 231–34. https://www.jstor.org/stable/3611225.