# v02.2
# st 02.04.2025 draft
# čt 03.04.2025 draft


# 1. Zadání: Vypsat všechna 3-ciferná čísla v poziční soustavě o základu n
# 2. Zadání: Vypsat všechna k-ciferná čísla v poziční soustavě o základu n


# Rekurzivni generovani
# na prikladu generovani k-tic

# kus uvahy: mame nagenerovat k-tice napr k = 3,
# to lze udelat lehce pomoci 3 vnorenych for cyklu
# co kdyz je ale k parametr a nevime kolik for cyklu mame vytvorit?
# reseni rekurze

# 1.
# Zadání: Vypsat všechna k-ciferná čísla v poziční soustavě o základu n
# note: proc ne for cyklus?

import copy
# k = 4  # počet cifer
# n = 3  # číselná soustava
# c = [0] * k  # vytvářené číslo

# Řešení pomocí rekurze a dynamické délky pole (listu)


# def gen_k_tice_z_intervalu_append(k, n, c=[]):
#     """vypíše všechna k-ciferná čísla v poziční soustavě o základu "n",
#     "c" je vytvářené číslo"""

#     # list delky +1
#     c.append(-1)

#     # zastavovaci podminka
#     if len(c) == k:
#         for i in range(n):
#             c[-1] = i
#             print(c)

#     else:
#         for i in range(n):
#             c[-1] = i
#             gen_k_tice_z_intervalu_append(k, n, c)

#     c.pop()  # co se stane, kdyz tu nebude teno radek?


def gen_k_tice_z_intervalu_append(k, n, c=[]):
    """vypíše všechna k-ciferná čísla v poziční soustavě o základu "n",
    "c" je vytvářené číslo"""

    # list delky +1
    c.append(-1)

    for i in range(n):
        # zastavovaci podminka
        if len(c) == k:
            c[-1] = i
            print(c)
        else:
            c[-1] = i
            gen_k_tice_z_intervalu_append(k, n, c)

    c.pop()  # co se stane, kdyz tu nebude teno radek?


print("------------------- gen_k_tice_z_intervalu_append(k, n, [])")
gen_k_tice_z_intervalu_append(3, 3, [])

# kvuli def parametru v def funkci, neni prazdny list treba
gen_k_tice_z_intervalu_append(3, 3)

gen_k_tice_z_intervalu_append(2, 4, [])


# 2.
# Zadání: Vypsat všechna k-ciferná čísla v poziční soustavě o základu n,
# bez opakování číslic v čísle
# (teď stačí i hodně naivní/neefektivní řešení)

# hodne naivni a ne moc chytry zpusob metody generuj (vše) a testuj
# generuji vse i co nechci vs prorezavani
# druhý "extrém", generuji právě jen to co chci;
# což často neumím; řešením je prořezávání slepých větví;
# snahou je slepou větev zaříznout, co nejdříve to jde -> lepší efektivita


def gen_k_tice_z_intervalu_no_rep(k, n, c=[]):
    """vypíše všechna k-ciferná čísla v poziční soustavě o základu "n",
    bez opakování číslic "c" je vytvářené číslo"""

    c.append(-1)

    for i in range(n):
        
        if i not in c:
            c[-1] = i

            if len(c) == k:
                print(c)
            else:
                gen_k_tice_z_intervalu_no_rep(k, n, c)
    c.pop()


print("------------------- gen_k_tice_z_intervalu_no_rep(3, 4, [])")
gen_k_tice_z_intervalu_no_rep(3, 4, [])


# 3. Zadání: Vypsat všechna k-ciferné rostoucí celočíselné (uspořádané) posloupnosti
# o zakladu n tj. v intervalu <0, n-1>
# note: všiměme si, že v zadání jsme slovo "číslo" nahradili (obecnějším) slovem "posloupnost"


def gen_growing_sequence(k, min_range, max_range, c=[]):
    """vypíše všechny k-ciferné rostoucí celočíselné posloupnosti v intervalu <0, n-1>"""

    c.append(-1)
    for i in range(min_range, max_range):
        if len(c) == k:
            c[-1] = i
            print(c)
        else:
            c[-1] = i
            gen_growing_sequence(k, i + 1, max_range, c)

    c.pop()


print("------------------- gen_growing_sequence(n, min_range, max_range, c)")
gen_growing_sequence(3, 0, 4, [])
gen_growing_sequence(3, 0, 5, [])
gen_growing_sequence(3, 0, 3, [])
gen_growing_sequence(4, 0, 3, [])


# 4. Zadání: Vypsat všechna k ciferné neklesajicí posloupnosti v intervalu <0, n-1>
def gen_non_decreasing_sequence(k, min_range, max_range, c):
    """vypíše všechny k ciferné neklesající posloupnosti v intervalu <0, n-1>"""

    c.append(-1)
    for i in range(min_range, max_range):
        if len(c) == k:
            c[-1] = i
            print(c)
        else:
            c[-1] = i
            gen_non_decreasing_sequence(k, i, max_range, c)

    c.pop()


print("------------------- gen_non_decreasing_sequence(n, min_range, max_range, c)")
# gen_non_decreasing_sequence(n=5, min_range=0, max_range=5, c=[])
gen_non_decreasing_sequence(2, 0, 3, [])
gen_non_decreasing_sequence(3, 0, 3, [])
gen_non_decreasing_sequence(3, 0, 4, [])


# 5. Zadání: Vypsat všechny k ciferné posloupnosti skládající
# se z prvků dané množiny S
# prvky z mnoziny se v posloupnosti mohou opakovat
# napr. mnozina S = {"a", "b"} posloupnost k=3 muze byt ["a", "a", "b"], ["b", "a", "b"]


def gen_sequence_from_set(k, s, c=[]):
    """vypíše všechny k-ciferné posloupnosti skládající se z prvků dané množiny s;
    prvky z mnoziny se v posloupnosti mohou opakovat"""

    c.append(-1)
    for i in s:
        if len(c) == k:
            c[-1] = i
            print(c)
        else:
            c[-1] = i
            gen_sequence_from_set(k, s, c)

    c.pop()


print("------------------- gen_sequence_from_set(n, s, c)")
gen_sequence_from_set(3, [3, -2, 5, "x"], [])
gen_sequence_from_set(3, [3, -2, "x"], [])


# 6. Zadání: Vypsat všechna k-ciferné (stále uspořádané) posloupnosti
# skládající se z prvků dané množiny,
# každý prvek množiny má zadán maximální počet opakování
# (pocet opakovani je unikatni pro kazdy prvek mnoziny)


# Řešení je (jedno z mnoha) použít dictionary pro uchování prvků množiny
# a poctu aktulně možných použití
# Dalsi Řešení je použít 2D list pro uchování prvků množiny a aktulně možných použití


def gen_sequence_from_set_limited_rep_dic(k, d, c=[]):
    """vypíše všechny k ciferné posloupnosti skládající se z prvků dané množiny,
    každý prvek (multi)množiny má zadán maximální počet opakování"""

    c.append(0)
    for i in d:
        if d[i] >= 1:
            if len(c) == k:
                c[-1] = i
                print(c)
            else:
                c[-1] = i
                d[i] -= 1
                gen_sequence_from_set_limited_rep_dic(k, d, c)
                d[i] += 1

    c.pop()


print("------------------- gen_sequence_from_set_limited_rep_dic(n, d, c)")

k = 3

# d { klic : pocetOpakovani}
d = {1: 2, "x": 5, 0: 1}

# for key, value in d.items():
#     print(f"{key} {value}")

gen_sequence_from_set_limited_rep_dic(k, d, [])

d = {1: 2, "x": 5, 0: 0}
gen_sequence_from_set_limited_rep_dic(k, d, [])

d = {1: 2, "x": 5, 0: 1, "d": 1, "A": 1}
gen_sequence_from_set_limited_rep_dic(k, d, [])

k = 2
gen_sequence_from_set_limited_rep_dic(k, d, [])


# 7. Zadání: Vypsat všechna k-prvkové multiMNOŽINY (neuspořadané k-tice)
# skládající se z prvků dané množiny,
# každý prvek množiny má zadán maximální počet opakování
#


def gen_sequence_from_set_limited_rep_list(k, d, min_range, max_range, c=[]):
    """vypíše všechny n ciferné nesupořádané n-tice
    skládající se z prvků dané množiny,
    každý prvek (multi)množiny/neuspořádané n-tice má zadán maximální počet opakování"""

    for i in range(min_range, max_range):
        if d[i][1] >= 1:
            c.append(0)
            c[-1] = d[i][0]

            if len(c) == k:
                print(c)
            else:
                d[i][1] -= 1
                gen_sequence_from_set_limited_rep_list(k, d, i, max_range, c)
                d[i][1] += 1

            c.pop()
        else:
            if i < max_range:
                gen_sequence_from_set_limited_rep_list(k, d, i + 1, max_range, c)


print("------------------- gen_sequence_from_set_limited_rep(n, d, c)")

k = 7  # n - velikost výběru (množiny)
# 3 uspořadané dvojice [prvek množiny, maximální počet opakování prvku ve výběru]
p = [[1, 2], ["x", 5], [0, 2]]

gen_sequence_from_set_limited_rep_list(k, p, min_range=0, max_range=len(p), c=[])

k = 2  # n - velikost výběru (množiny)
# 3 uspořadané dvojice [prvek množiny, maximální počet opakování prvku ve výběru]
p = [[1, 2], ["x", 5], [0, 2]]

gen_sequence_from_set_limited_rep_list(k, p, min_range=0, max_range=len(p), c=[])


# 8. Napište funkci, která vypíše všechny rozklady čísla N
# na součet kladných celých sčítanců
#
# note: co je zastavovaci podminka rekurze?
# V predchozich rekurzivnich generovani to byla delka posloupnosti,
# zde je to soucet poslupnosti


def rozloz_cislo(n, rozklad=[]):
    """Rozlozi cislo n na soucet kladnych scitancu; nevynechava permutace rozkladu"""
    rozklad.append(-1)

    for i in range(1, n + 1):
        rozklad[-1] = i
        # opakovane pocitani sum, neni to zbytecne/neefektivni?
        soucet = sum(rozklad)

        if soucet == n:
            print(rozklad)
        elif soucet < n:
            rozloz_cislo(n, rozklad)
        else:
            # bude kod fungovat i bez elif s > n?
            # co prinasi/optimalizuje v algoritmu?
            break

    rozklad.pop()


rozloz_cislo(5)
rozloz_cislo(3)
rozloz_cislo(1)
rozloz_cislo(10)


def rozloz_cislo2(zbyva, rozklad=[]):
    """Rozlozi cislo n na soucet kladnych scitancu; nevynechava permutace rozkladu
    Eviduji zbytek rozkladu, ktery je treba dogenerovat,
    neni nutne opakovane pocitat sum(n) a
    ve for cyklu neiteruji pres nadbytecne hodnoty"""

    rozklad.append(-1)

    for i in range(1, zbyva + 1):
        rozklad[-1] = i
        # print(rozklad)

        if zbyva == i:
            print(rozklad)
        else:
            rozloz_cislo2(zbyva - i, rozklad)

    rozklad.pop()


rozloz_cislo2(1)
rozloz_cislo2(3)
rozloz_cislo2(5)


# 8.2 nalézt všechny takové celociselne rozklady (usporadane k-tice) čísla N,
# které mají délku K pro zadané číslo K
def rozloz_cislo_delka_K(zbyva, k, rozklad=[]):
    """Rozlozi cislo n na soucet kladnych scitancu dane delky (mereno poctem scitancu);
    nevynechava permutace rozkladu"""

    rozklad.append(-1)

    for i in range(1, zbyva + 1):
        rozklad[-1] = i
        # print(rozklad)

        if (zbyva == i) and (len(rozklad) == k):
            print(rozklad)
        else:
            if len(rozklad) < k:
                rozloz_cislo_delka_K(zbyva - i, k, rozklad)

    rozklad.pop()


rozloz_cislo_delka_K(6, 3)
rozloz_cislo_delka_K(6, 2)
rozloz_cislo_delka_K(6, 1)
rozloz_cislo_delka_K(6, 7)


# 8.3 nalézt všechny rozklady daného čísla N na součet kladných celých sčítanců
# bez permutací sčítanců
# note: předchozí kody generují permutované n-tice stejných sčítanců
# např. [4, 1] = 5 a [1, 4] = 5
# nebo [1, 2, 2], [2, 1, 2], [2, 2, 1] = 5
# nyní požadujeme řešení bez těchto permutací

# řešení: generovat neklesající posloupnosti


def rozloz_cislo_bez_permutaci(n, rozklad=[]):
    """Rozlozi cislo n na soucet kladnych scitancu; vynechava permutace rozkladu"""
    if len(rozklad) == 0:
        minRange = 1
    else:
        minRange = rozklad[-1]

    rozklad.append(-1)

    for i in range(minRange, n + 1):
        rozklad[-1] = i
        s = sum(rozklad)

        if s == n:
            print(rozklad)
        elif s < n:
            rozloz_cislo_bez_permutaci(n, rozklad)
        else:
            break

    rozklad.pop()


rozloz_cislo_bez_permutaci(5)
rozloz_cislo_bez_permutaci(3)
rozloz_cislo_bez_permutaci(1)
rozloz_cislo_bez_permutaci(10)


def rozloz_cislo_bez_permutaci2(n, minRange=1, rozklad=[]):
    """Rozlozi cislo n na soucet kladnych sčítanců; vynechava permutace rozkladu"""

    rozklad.append(-1)

    for i in range(minRange, n + 1):
        rozklad[-1] = i
        s = sum(rozklad)

        if s == n:
            print(rozklad)
        elif s < n:
            rozloz_cislo_bez_permutaci2(n, i, rozklad)
        else:
            break

    rozklad.pop()


rozloz_cislo_bez_permutaci2(5)
rozloz_cislo_bez_permutaci2(3)
rozloz_cislo_bez_permutaci2(1)
rozloz_cislo_bez_permutaci2(10)


# 9. Bankomat


# 10. Vypiste vsechny permutace dane mnoziny S (zadane listem)
def perm(s, unUsed, p=[]):
    """Vypise vsechny permutace dane mnoziny S (zadane listem)"""
    if any(unUsed):
        p.append(-1)

        for i in range(len(s)):
            if unUsed[i]:
                p[-1] = s[i]
                unUsed[i] = False
                perm(s, unUsed, p)
                unUsed[i] = True
        p.pop()
    else:
        print(p)


s = ["a", "b", "c"]
unUsed = [True] * len(s)
print(unUsed)
# print(any(unUsed))
perm(s, unUsed)

s = ["a", "b", "c", "x"]
unUsed = [True] * len(s)
print(unUsed)

perm(s, unUsed)