Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 17: Ứng dụng sinh các hoán vị

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

Chöông 17 – ÖÙNG DUÏNG SINH CAÙC HOAÙN VÒ

ÖÙng duïng naøy minh hoïa söï söû duïng caû hai loaïi danh saùch: danh saùch toång

quaùt vaø DSLK trong maûng lieân tuïc. ÖÙng duïng naøy seõ sinh ra n! caùch hoaùn vò cuûa

n ñoái töôïng moät caùch hieäu quaû nhaát. Chuùng ta goïi caùc hoaùn vò cuûa n ñoái töôïng

khaùc nhau laø taát caû caùc phöông aùn thieát laäp chuùng theo moïi thöù töï coù theå coù.

Chuùng ta coù theå choïn baát kyø ñoái töôïng naøo trong n ñoái töôïng ñaët taïi vò trí ñaàu

tieân, sau ñoù coù theå choïn baát kyø trong n-1 ñoái töôïng coøn laïi ñaët taïi vò trí thöù hai,

vaø cöù theá tieáp tuïc. Caùc choïn löïa naøy ñoäc laäp nhau neân toång soá caùch choïn löïa laø:

n x (n-1) x (n-2) x ... x 2 x 1 = n!

Hình 17.1- Sinh caùc hoaùn vò cho {1, 2, 3, 4}

17.1. YÙ töôûng

Chuùng ta xaùc ñònh caùc hoaùn vò qua caùc nuùt treân caây. Ñaàu tieân chæ coù 1 ôû goác

caây. Chuùng ta coù hai hoaùn vò cuûa {1, 2} baèng caùch ghi 2 beân traùi, sau ñoù beân phaûi

cuûa 1. Töông töï, saùu hoaùn vò cuûa {1, 2, 3} coù ñöôïc töø (2, 1) vaø (1, 2) baèng caùch

theâm 3 vaøo caû ba vò trí coù theå (traùi, giöõa, phaûi). Nhö vaäy caùc hoaùn vò cuûa {1, 2, ...,

k} coù ñöôïc nhö sau:

Ñoái vôùi moãi hoaùn vò cuûa {1, 2, ..., k-1} chuùng ta ñöa caùc phaàn töû vaøo moät list.

Sau ñoù cheøn k vaøo moïi vò trí coù theå trong list ñoù ñeå coù ñöôïc k hoaùn vò khaùc nhau

cuûa {1, 2, ..., k}.

Giaûi thuaät naøy minh hoïa vieäc söû duïng ñeä quy ñeå hoaøn thaønh caùc coâng vieäc ñaõ

taïm hoaõn. Chuùng ta seõ vieát moät haøm, ñaàu tieân laø theâm 1 vaøo moät danh saùch roãng,

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

395

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

sau ñoù goïi ñeä quy ñeå theâm laàn löôït caùc soá khaùc töø 2 ñeán n vaøo danh saùch. Laàn goïi

ñeä quy ñaàu tieân seõ theâm 2 vaøo danh saùch chæ chöùa coù 1, giaû söû theâm 2 beân traùi

cuûa 1, vaø trì hoaõn caùc khaû naêng theâm khaùc (nhö laø theâm 2 beân phaûi cuûa 1), ñeå

goïi ñeä quy tieáp. Cuoái cuøng, laàn goïi ñeä quy thöù n seõ theâm n vaøo danh saùch. Baèng

caùch naøy, baét ñaàu töø moät caáu truùc caây, chuùng ta phaùt trieån moät giaûi thuaät trong ñoù

caây naøy trôû thaønh moät caây ñeä quy.

17.2. Tinh cheá

Chuùng ta seõ phaùt trieån giaûi thuaät treân cuï theå hôn. Haøm theâm caùc soá töø 1 ñeán n

ñeå sinh n!hoaùn vò seõ ñöôïc goïi nhö sau:

permute(1, n)

Giaû söû ñaõ coù k-1 soá ñaõ ñöôïc theâm vaøo danh saùch, haøm sau seõ theâm caùc soá coøn

laïi töø k ñeán n vaøo danh saùch:

void permute(int k,int n)

/*

pre: Töø 1 ñeán k - 1 ñaõ coù trong danh saùch caùc hoaùn vò;

post: Cheøn caùc soá nguyeân töø k ñeán n vaøo danh saùch caùc hoaùn vò.

*/

{

for // vôùi moãi vò trí trong k vò trí coù theå trong danh saùch.

{

// Cheøn k vaøo vò trí naøy.

if (k == n) process_permutation;

else permute(k + 1, n);

// Laáy k ra khoûi vò trí vöøa cheøn.

}

Khi coù ñöôïc moät hoaùn vò ñaày ñuû cuûa {1, 2, ..., n}, chuùng ta coù theå in keát

quaû, hoaëc gôûi keát quaû nhö laø thoâng soá vaøo cho moät baøi toaùn naøo khaùc, ñoù laø nhieäm

vuï cuûa haøm process_permutation.

17.3. Thuû tuïc chung

Ñeå chuyeån giaûi thuaät thaønh chöông trình C++, chuùng ta coù caùc teân bieán nhö

sau: danh saùch caùc soá nguyeân permutation chöùa hoaùn vò cuûa caùc soá; new_entry,

thay cho k, laø soá nguyeân seõ ñöôïc theâm vaøo; vaø degree, thay cho n, laø soá caùc

phaàn töû caàn hoaùn vò.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

396

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

void permute(int new_entry, int degree, List<int> &permutation)

/*

pre: permutation chöùa 1 hoaùn vò vôùi caùc phaàn töû töø 1 ñeán new_entry - 1.

post: Moïi hoaùn vò cuûa degreephaàn töû ñöôïc taïo neân töø hoaùn vò ñaõ coù vaø seõ ñöôïc xöû lyù trong haøm

process_permutation.

uses: haøm permute moät caùch ñeä quy, haøm process_permutation, vaø caùc haøm cuûa List.

*/

{

for (int current = 0; current < permutation.size() + 1; current++) {

permutation.insert(current, new_entry);

if (new_entry == degree)

process_permutation(permutation);

else

permute(new_entry + 1, degree, permutation);

permutation.remove(current, new_entry);

}

Haøm treân ñaây coù theå söû duïng vôùi baát kyø hieän thöïc naøo cuûa danh saùch maø

chuùng ta ñaõ laøm quen (DSLK söû duïng con troû, danh saùch lieân tuïc, DSLK trong

maûng lieân tuïc). Vieäc xaây döïng öùng duïng ñaày ñuû ñeå sinh caùc hoaùn vò xem nhö baøi

taäp. Tuy nhieân chuùng ta seõ thaáy raèng öu ñieåm cuûa DSLK trong maûng lieân tuïc raát

thích hôïp ñoái vôùi baøi toaùn naøy trong phaàn tieáp theo döôùi ñaây.o3

17.4. Toái öu hoùa caáu truùc döõ lieäu ñeå taêng toác ñoä cho chöông trình

sinh caùc hoaùn vò

n! taêng raát nhanh khi n taêng. Do ñoù soá hoaùn vò coù ñöôïc seõ raát lôùn. ÖÙng duïng

treân laø moät trong caùc öùng duïng maø söï toái öu hoùa ñeå taêng toác ñoä chöông trình raát

ñaùng ñeå traû giaù, ngay caû khi aûnh höôûng ñeán tính deã ñoïc cuûa chöông trình. Chuùng

ta seõ duøng DSLK trong maûng lieân tuïc coù keøm moät chuùt caûi tieán cho baøi toaùn treân.

Chuùng ta haõy xem xeùt moät vaøi caùch toå chöùc döõ lieäu theo höôùng laøm taêng toác ñoä

chöông trình caøng nhanh caøng toát. Chuùng ta söû duïng moät danh saùch ñeå chöùa caùc

soá caàn hoaùn vò. Moãi laàn goïi ñeä quy ñeàu phaûi caäp nhaät caùc phaàn töû trong danh

saùch. Do chuùng ta phaûi thöôøng xuyeân theâm vaø loaïi phaàn töû cuûa danh saùch, DSLK

toû ra thích hôïp hôn danh saùch lieân tuïc. Maët khaùc, do toång soá phaàn töû trong danh

saùch khoâng bao giôø vöôït quaù n, chuùng ta neân söû duïng DSLK trong maûng lieân tuïc

thay vì DSLK trong boä nhôù ñoäng.

Hình 17.2 minh hoïa caùch toå chöùc caáu truùc döõ lieäu. Hình treân cuøng laø DSLK

cho hoaùn vò (3, 2, 1, 4). Hình beân döôùi bieåu dieãn hoaùn vò naøy trong DSLK trong

maûng lieân tuïc. Ñaëc bieät trong hình naøy, chuùng ta nhaän thaáy, trò cuûa phaàn töû ñöôïc

theâm vaøo cuõng chính baèng chæ soá cuûa phanà töû trong array, neân vieäc löu caùc trò naøy

khoâng caàn thieát nöõa. (Chuùng ta chuù yù raèng, trong giaûi thuaät ñeä quy, caùc soá ñöôïc

theâm vaøo danh saùch theo thöù töï taêng daàn, neân moãi phaàn töû seõ chieám vò trí trong

maûng ñuùng baèng trò cuûa noù; caùc hoaùn vò khaùc nhau cuûa caùc phaàn töû naøy ñöôïc phaân

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

397

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

bieät bôûi thöù töï cuûa chuùng trong danh saùch, ñoù chính laø söï khaùc nhau veà caùch noái

caùc tham chieáu). Cuoái cuøng chæ coøn caùc tham chieáu laø caàn löu trong maûng (hình

döôùi cuøng trong hình 17.2). Node 0 duøng ñeå chöùa ñaàu vaøo cuûa DSLK trong maûng

lieân tuïc. Trong chöông trình döôùi ñaây chuùng ta vieát laïi caùc coâng vieäc theâm vaø loaïi

phaàn töû trong danh saùch thay vì goïi caùc phöông thöùc cuûa danh saùch ñeå taêng hieäu

quaû toái ña.

(entry)

(next)

Hình 17.2 – Caáu truùc döõ lieäu chöùa hoaùn vò

17.5. Chöông trình

Chuùng ta coù haøm permuteñaõ ñöôïc caûi tieán:

void permute(int new_entry, int degree, int *permutation)

/*

pre: permutation chöùa 1 hoaùn vò vôùi caùc phaàn töû töø 1 ñeán new_entry - 1.

post: Moïi hoaùn vò cuûa degreephaàn töû ñöôïc taïo neân töø hoaùn vò ñaõ coù vaø seõ ñöôïc xöû lyù trong haøm

process_permutation.

uses: haøm permute moät caùch ñeä quy, haøm process_permutation.

*/

{

int current = 0;

do {

permutation[new_entry] = permutation[current];

permutation[current] = new_entry;

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

398

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

if (new_entry == degree)

process_permutation(permutation);

else

permute(new_entry + 1, degree, permutation);

permutation[current] = permutation[new_entry];

current = permutation[current];

} while (current != 0);

}

Chöông trình chính thöïc hieän caùc khai baùo vaø khôûi taïo:

main()

/*

pre: Ngöôøi söû duïng nhaäp vaøo degree laø soá phaàn töû caàn hoaùn vò.

post: Moïi hoaùn vò cuûa degree phaàn töû ñöôïc in ra.

*/

{

int degree;

int permutation[max_degree + 1];

cout << "Number of elements to permute? ";

cin >> degree;

if (degree < 1 || degree > max_degree)

cout << "Number must be between 1 and " << max_degree << endl;

else {

permutation[0] = 0;

permute(1, degree, permutation);

}

Danh saùch permutation laøm thoâng soá cho haøm process_permutation chöùa

caùch noái keát caùc phaàn töû trong moät hoaùn vò, chuùng ta coù theå in caùc soá nguyeân cuûa

moät caùch hoaùn vò nhö sau:

void process_permutation(int *permutation)

/*

pre: permutation trong caáu truùc lieân keát bôûi caùc chæ soá.

post: permutation ñöôïc in ra.

*/

{

int current = 0;

while (permutation[current] != 0) {

cout << permutation[current] << " ";

current = permutation[current];

}

cout << endl;

}

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

399

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

400