Jypiter Notebook, Anaconda

• interaktívny zošit (Start/Jupyter Notebook)

https://www.anaconda.com/distribution/#download-section

Prvá možnosť je vygenerovať všetky n-prvkové kombinácie s opakovaním a následne pred výpisom testovať či sa nejaká hodnota neopakuje

n = 3
k = 4

post = [0]*n #n-prvkova postupnost
 
def neopakuje(): #vrati True ak sa ziadne cislo neopakuje
	for i in range(n):
		for j in range(i+1,n):
			if post[i] == post[j]:
				return False
	return True
 
 
def generuj1(uroven): #vyskusaj na danej urovni vsetky moznosti
	if uroven == n: #mame celu postupnost
		if neopakuje():
			print(post)
		return
	for i in range(1, k+1): #cisla 1 az k
		post[uroven] = i
		generuj1(uroven+1)
 
generuj1(0) #generuj od zaciatku, prveho prvku

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

Tento kód má zložitosť O(k^n . n^2) - pre každú možnosť s opakovaním overí všetky dvojice prvkov

Druhá možnosť je testovať priebežne pri skúšaní hodnoty

post = [0]*n #n-prvkova postupnost

def generuj2(uroven): #vyskusaj na danej urovni vsetky moznosti
	if uroven == n: #mame celu postupnost
		print(post)
		return
	for i in range(1, k+1): #cisla 1 az k
		#otestujeme ci hodnota i uz bola
		if not i in post[:uroven] : #ci hodnota i uz bola v uz vyplnenej casti
			post[uroven] = i
			generuj2(uroven+1)

generuj2(0) #generuj od zaciatku, prveho prvku

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

Zložitosť O ( (n!/(n-k)! . n)

Najefektívnejšie je priamo generovať už len postupnosti bez opakovania, pamätať si ktorá hodnota už bola použitá (v pomocnom poli nebolo)

post = [0]*n #n-prvkova postupnost
nebolo = [True]*(k+1) #na zaciatku este neboli pouzite ziadne hodnoty

def generuj3(uroven): #vyskusaj na danej urovni vsetky moznosti
	if uroven == n: #mame celu postupnost
		print(post)
		return
	for i in range(1, k+1): #cisla 1 az k
		#otestujeme ci hodnota i uz bola
		if nebolo[i]: #ci hodnota i uz bola v uz vyplnenej casti
			post[uroven] = i
			nebolo[i] = False #hodnota i uz je pouzita
			generuj3(uroven+1)
			nebolo[i] = True #uvolnene

generuj3(0) #generuj od zaciatku, prveho prvku
	

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]