3943 - Cerc5

Cerința

Să se genereze toate permutările circulare ale unui șir de numere naturale, unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive.

Date de intrare

Programul citește de la tastatură un șir de n numere naturale.

Date de ieșire

Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie.

Restricții și precizări

• 1 ⩽ n ⩽ 10
• Numerele din șir sunt naturale și distincte

Exemplu 1

Intrare

1 2 3

Iesire

1 2 3
2 3 1
3 1 2

Rezolvare

<syntaxhighlight lang="python" line> def citeste_date():

   try:
       sir = list(map(int, input("Introduceți șirul de numere naturale, separate prin spațiu: ").split()))
       return sir
   except ValueError:
       return None

def valideaza_date(sir):

   if not (1 <= len(sir) <= 10):
       return False
   if not all(isinstance(num, int) and num >= 0 for num in sir):
       return False
   if len(sir) != len(set(sir)):
       return False
   return True

def permutari_circulare(sir):

   n = len(sir)
   permutari = []

   def backtrack(current_perm, used):
       if len(current_perm) == n:
           if (current_perm[0] == sir[0]):
               permutari.append(current_perm[:])
           return

       for i in range(n):
           if not used[i]:
               used[i] = True
               current_perm.append(sir[i])
               backtrack(current_perm, used)
               current_perm.pop()
               used[i] = False

   used = [False] * n
   backtrack([], used)

   return permutari

def main():

   sir = citeste_date()
   
   if sir is None or not valideaza_date(sir):
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   print("Datele de intrare corespund restricțiilor impuse.")
   permutari = permutari_circulare(sir)
   
   for perm in permutari:
       print(" ".join(map(str, perm)))

if __name__ == "__main__":

   main()

</syntaxhighlight>