Rekurzivní nalezení kombinací v poli – Java – Fórum – Programujte.com

Zdravím vás,

potřebovala bych poradit jak najít rekurzivní algoritmus, který v dané čtvercové matici čísel vybere všechny kombinace tak, že z každého řádku vybere právě jedno číslo, přičemž se nesmí vybírat v dalším řádku číslo s indexem sloupce stejným jako index sloupce již vybraného čísla v některém z předchozích řádků. (tzn. že v každém výběru/kombinaci bude právě tolik čísel jako je počet řádků/sloupců v matici a nesmí se vybrat čísla která leží v matici "pod sebou").

Mockrát předem děkuji, trápím se s tím už delší dobu.

Tebe v podstatě nezajímá co je v té matici, chceš najít všechny permutace indexů.
Příklad jak to třeba udělat rekurzivně: Budeš mít pole velikosti n. Do něj si budeš značit, jestli jsi už daný index použila, na začátku nebude použito nic. Rekurzivně pak budeš přidávat vždy nový index a jakmile dojdeš na konec, tak si jej zapamatuješ.
Pseudokód(ne tak úplně ;-):

n = 4

pouzite = n * [False]



def vsechnyPermutace(permutace, delka):

	global n, pouzite

	for j in range(n):

		if pouzite[j]:

			continue

		else:

			pouzite[j] = True

			vsechnyPermutace(permutace+[j], delka+1)

			pouzite[j] = False

	if n == delka:

		print permutace