Backtracking

Generare Permutări

Posted by Feroviarul on

Aspecte teoretice:

Permutarea este un concept matematic care se referă în mod uzual la numărul de posibilități de rearanjare al unei liste ordonate de valori sau obiecte. Cel mai simplu exemplu de permutare este dat de către o anagramă; de exemplu, literele cuvântului CARTE (toate distincte între ele) pot fi rearanjate formând cuvântul TRACE sau ECART.
C A R T E
T R A C E
E C A R T
Așadar o permutare poate fi înțeleasă ca unul din n! moduri de a ordona liniar o mulțime. Însă în general nu este necesar ca obiectele permutate să fie ordonate liniar. De pildă, într-o echipă de funcționari, aceștia pot schimba între ei locurile dintr-un birou, locuri care ar putea să nu fie dispuse în linie. Un alt exemplu este cel al unor bile diferit colorate, înșirate pe o sârmă închisă. Această situație va conduce la definiția abstractă, matematică, a permutării, în care nu mai sunt implicate ordinea sau alte determinări ale subiecților permutați.
Conceptul este studiat în cadrul combinatoricii. Aici conceptul poate extins prin conceptul de k-permutări sau aranjamente care arată numărul submulțimilor ordonate ale unei mulțimi date.
Conceptul abstract de permutare este folosit în cadrul algebrei abstracte în studiul structurilor algebrice cu operații n-are.
Problemă:
Scrieți programe pentru generarea permutărilor de n elemente ale unei mulțimi.
Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace PermutariCS
{
    class Program
    {
        static bool ConditiiContinuare(int[] x, int k)
        {
            bool atac = false;
            int i = 1;
            while (!atac && i < k)
                if (x[i] == x[k])
                    atac = true;
                else
                    i++;
            return !atac;
        }
 
        static void ScrieSolutia(int[] x, int n, int nsol)
        {
            Console.WriteLine("Solutia " + nsol + " este: ");
 
            for (int i = 1; i <= n; i++)
            {
                Console.Write(x[i]);
            }
            Console.ReadLine();
        }
 
        static void Main(string[] args)
        {
            int n, k, nsol;
            bool buna;
            int[] x = new int[50];
            Console.WriteLine("Problema permutarilor");
            Console.Write("Dati numarul n ");
            n = Convert.ToInt32(Console.ReadLine());
            k = 1;
            x[k] = 0;
            nsol = 0;
            while (k > 0)
            {
                buna = false;
                while (!buna && x[k] < n)
                {
                    x[k]++;
                    if (ConditiiContinuare(x, k))
                        buna = true;
                }
                if (buna)
                    if (k == n)
                    {
                        nsol++;
                        ScrieSolutia(x, n, nsol);
                    }
                    else
                    {
                        k++;
                        x[k] = 0;
                    }
                else
                    k--;
            }
        }
    }
}
Logo_VB
Cod Sursa VB
Imports System.Math
Module Module1
    Dim x(51) As String
    Dim n, k, nsol As Integer
    Dim buna As Boolean
 
    Function ConditiiContinuare(ByVal k As Integer)
        Dim atac As Boolean
        atac = False
        Dim i As Integer
        i = 1
        While (Not atac And i < k)
            If (x(i) = x(k)) Then
                atac = True
            Else
                i = i + 1
            End If
        End While
        Return Not atac
    End Function
 
    Sub ScrieSolutie()
        nsol = nsol + 1
        Console.WriteLine("Solutia " & nsol & " este: ")
        For i = 1 To n
            Console.Write(x(i))
        Next i
        Console.ReadLine()
    End Sub
 
    Sub Main()
        Console.WriteLine("Problema Permutarilor")
        Console.Write("Dati numarul n: ")
        n = Convert.ToInt32(Console.ReadLine())
        k = 1
        x(k) = 0
        nsol = 0
        While (k > 0)
            buna = False
            While (Not buna And x(k) < n)
                x(k) = x(k) + 1
                If (ConditiiContinuare(k)) Then
                    buna = True
                End If
            End While
            If (buna) Then
                If (k = n) Then
                    ScrieSolutie()
                Else
                    k = k + 1
                    x(k) = 0
                End If
            Else
                k = k - 1
            End If
        End While
    End Sub
 
End Module
Visual_C++_Icon
Cod Sursa C++
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <cmath>
 
using namespace std;
 
int x[51];
int k, n, nsol;
bool buna;
 
bool ConditiiContinuare(int k)
{
	 bool atac=false; 
	 int i=1;
	 while (!atac && i<k)
		   if (x[i]==x[k])
			  atac=true;
		   else i++;
	 return !atac;
}
 
void ScrieSolutia()
{
	 nsol++;
	 cout<<"Solutie "<<nsol<<" este:\n";
	 for (int i=1; i<=n; i++)
		 cout<<x[i];
	 cout<<endl;
	 getchar();
}
 
int main()
{
	cout<<"Problema generare permutari\n";
	cout<<"Dati numarul n: ";
	cin>>n;
	k=1;
	x[k]=0;
	nsol=0;
	while (k>0)
	  {
		  buna=false;
		  while (!buna && x[k]<n)
				{
				  x[k]++; 
				  if (ConditiiContinuare(k)) buna=true;
				  
				}
		  if (buna)
			 if (k==n)
				 ScrieSolutia(); 
			 else 
				  {
					k++; 
					x[k]=0; 
				  }
		  else
			  k--; 
	  }          
}
Java-Logo
Cod Sursa JAVA

 

import java.io.*;
class PermutariJAVA
    {
        static boolean ConditiiContinuare(int x[],int k)
        {
            boolean atac = false;
            int i = 1;
            while (!atac && i < k)
                if (x[i] == x[k])
                    atac = true;
                else
                    i++;
            return !atac;
        }        static void ScrieSolutia(int x[],int n,int nsol)
        {
            System.out.println(“Solutia ” + nsol + ” este: “);
            for (int i = 1; i <= n; i++)
            {
                System.out.println(x[i] + ” “);
            }
        }

        public static void main(String args[])
        {
          String line = null;
            int k,nsol;
            int n=0;
            boolean buna;
            int [] x = new int[50];
            System.out.println(“Problema permutarilor”);
            System.out.println(“Dati numarul n “);
            try
      {
          BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
          line = is.readLine();
          n = Integer.parseInt(line);
        }
        catch (NumberFormatException ex)
        {
          System.err.println(“Not a valid number: ” + line);
        }
        catch (IOException e)
        {
          System.err.println(“Unexpected IO ERROR: ” + e);
        }
            k = 1;
            x[k] = 0;
            nsol = 0;
            while (k > 0)
            {
                buna = false;
                while (!buna && x[k] <n)
                {
                    x[k]++;
                    if (ConditiiContinuare(x,k))
                        buna = true;
                }
                if (buna)
                    if (k == n)
                    {
                        nsol++;
                        ScrieSolutia(x, n,nsol);
                    }
                    else
                    {
                        k++;
                        x[k] = 0;
                    }
                else
                    k–;
            }
        }
    }

 

Rezultat:

permutari rezultat

Leave a comment