Kurš ir kurš? Es nezinu.
Dotas kopas S permutācija P ir virkne no kopas elementiem, kurā katrs kopas elements ir tieši vienu reizi.
Ja dota kopa {A,B}, tad permutācijas ir divas: A, B un B, A. Kopējais dažādo permutāciju skaits ir vienāds ar faktoriāli no kopas izmēra. Faktoriālis ir funkcija no nenegatīva vesela skaitļa, kuru atpakaļejoši definē šādi: F(0)=1, F(x>0)=x*F(x-1). Šai funkcijai lieto speciālu apzīmējumu: F(x)=x!. Funkcija ātri aug jeb, tikai nedaudz palielinot x, x! kļūst daudz lielāks. Var rakstīt, ka kopai S permutāciju skaits ir |S|!.
Permutāciju sakarā interesanti ir divi uzdevumi: visu permutāciju ģenerēšana un to attēlošana. Ja dota palielāka kopa, tadvar gadīties, ka visas permutācijas parādīt ir grūti.
Viena no permutāciju emocionāli simboliskām vērtībām ir to pielietojums dažādu sajukumu attēlojumā. Piemēram, ja man sajūk Kauliņš ar Baško, tad nav grūti iedomāties, ka savā realitātē nevaru atšķirt Kauliņa un Baško kopas divas permutācijas: Kauliņš, kam seko Baško, vai otrādo: Baško, aiz kura nāk Kauliņš. Šāds piemērs iegaismo vidējā bloku lasītāja īsteno sajukumu: Baško ir spilgta individualitāte; savukārt Kauliņš, divi it kā atšķirami Bankovski, Šlāpins un Lediņš, viņam bieži šķiet viena persona.
Turpinājumā ilustrācija, no kuras rindām lasītājam vajadzētu spēt saprast, kādas iespējas ir viņa sajukumam:
Lai iegūtu šo ilustrāciju, mēs lietojām Dr. Donalda Knuta grāmatā Programmēšanas māksla nodaļā 7.2.1.2 publicēto algoritmu L, kas apmeklē visas permutācijas leksikogrāfiskā secībā. Mēs pielāgojam to kā secību lietojot iedomātu, varbūt precīzu, vecuma kārtību: Kauliņš, Lediņš, Šlāpins, Bankovskis P., Bankovskis P. vecākais. Tad mums likās, kas izskatās pārāk sakārtoti un mēs lietojām gadījumskaitļu ģeneratoru, kas par tādu izliekās, lai spēcinātu sajukuma iespaidu. Par spīti baumām, šis izejas kods nekad nav publicēts Rīgas laikā vai Times magazine, bet tiek publicēts šeit kā Pielikums A.
Starp citu, iedomājieties, kas notiktu, ja papildus šiem pieciem sāktu jukt arī Baško.
Pielikums A
#briidinaajums: nemaacieties no shejienes programmeet.
#kaut gan idejas te ir.
#iekljaujam imidzhus
import Image
#iekljaujam gadiijumotaajus
import random
#dotaa permutaacija, mees apskatiisim tikai taas kopas,
#kuraas ir vismaz viens elements un visi elementi dazhaadi
a = [0,1,2,3,4]
#permutaacijas peedeejais elements
n = len(a) - 1 # Knuts saka n, bet domaa masiiva beigas
#mazaas elementbildes, tikpat daudz, cik elementu
kaadas_bildes_izmantojam = ["0.jpg", "1.jpg",
"2.jpg", "3.jpg", "4.jpg"]
#paarveersham par imidzhiem.
imidzhi = [Image.open(bilde) for bilde in kaadas_bildes_izmantojam]
def faktoriaalis(x):
if x == 0: return 1
return x * faktoriaalis(x - 1)
permutaaciju_skaits = faktoriaalis(len(a))
vienas_sejas_izmeers = (30, 30)
#visi imidzhi pareizaa izmeeraa
for imidzhs in imidzhi:
#man shkjiet, ka var rakstiit imidzhs.size
#!= vienas_sejas_izmeers, bet par sho esmu droshs
if (imidzhs.size[0] != vienas_sejas_izmeers[0]
or imidzhs.size[1] != vienas_sejas_izmeers[1]):
imidzhs.resize(vienas_sejas_izmeers, Image.ANTIALIAS)
#starp bildeem buus spraugas
spraugas_platums = 2
kopeejais_izmeers = (vienas_sejas_izmeers[0]*len(a)
+ (len(a) + 1) * spraugas_platums,
vienas_sejas_izmeers[1]*permutaaciju_skaits
+ (permutaaciju_skaits + 1) * spraugas_platums)
# jauns imidzhs, balts kaa mugura
galvenais_imidzhs = Image.new("RGB", kopeejais_izmeers,
(255, 255, 255))
#cik permutaacijas jau ir apskatiitas
skaiteekljis = 0
#ko tad iisti dariit ar katru permutaaciju
def shito_dariit(permutaacija):
global skaiteekljis
no_augshas = ((skaiteekljis+1) * spraugas_platums
+ skaiteekljis*(vienas_sejas_izmeers[1]))
for i in range(len(permutaacija)):
no_kreisaas = ((i+1) * spraugas_platums
+ i * vienas_sejas_izmeers[0])
galvenais_imidzhs.paste(
imidzhi[permutaacija[i]],
(no_kreisaas, no_augshas))
skaiteekljis += 1; # gaidaam naakamo
permutaacijas = []
def noglabaat(permutaacija):
global permutaacijas
kopeetaa_permutaacija = []
# nevar pashreizeejo permutaaciju noglabaat vajag glabaat kopiju
for elements in permutaacija:
kopeetaa_permutaacija.append(elements)
permutaacijas.append(kopeetaa_permutaacija)
#algoritms L, 7.2.1.2
def dariit_ar_katru_permutaaciju(ko_dariit):
while 1:
ko_dariit(a);
j = n - 1
# Knuts saka 0, bet vinja masiivi saakas ar 1 un beidzas ar n
while j != -1 and a[j] >= a[j+1]:
j -= 1
if (j == -1):
return
l = len(a) - 1
while a[j]>=a[l]:
l -= 1
(a[l],a[j])=(a[j],a[l])
k = j + 1
l = n
while k < l:
a[l], a[k] = a[k], a[l];
l -= 1;
k += 1;
dariit_ar_katru_permutaaciju(noglabaat);
def gadiijumot_masiivu(masiivs):
for indekss in range(len(masiivs)):
jaunaa_vieta = random.randint(0, len(masiivs)-1)
(masiivs[indekss], masiivs[jaunaa_vieta]) = (
masiivs[jaunaa_vieta], masiivs[indekss])
#lai permutaaciju sajukums neizskatiitos paaraak regulaars
gadiijumot_masiivu(permutaacijas)
for permutaacija in permutaacijas:
shito_dariit(permutaacija)
galvenais_imidzhs.save("permutaacijas.jpg", "JPEG");
