Dubbio sulla permutazione di un array di bit

[toni00c]

ciao ; ho la necessità di dover calcolare tutte le permutazioni di un array di N bit , ma non so come fare .

sulla rete ho trovato un articolo che però è un po ostico da capire


http://fwlab.com/en/permutazioni-dib...he-operazioni/

qualcuno ha qualche idea -codice o algoritmo da consigliarmi?

esiste un modo per calcolare direttamente la i-esima permutazione di un array di N bit ?

grazie

[hamming_burst]

se devi enumerare tutte le permutazioni sono tre righe di codice ed utilizza la tecnica backtrack, te la copio-incollo grezzamente è piuttosto banale (il funzionamento è un attimo più difficile capirlo, se interessa ne parliamo).

permutations (SET A, integer n, ITEM[] S, integer i)
	foreach c in A do 
		S[i] <- c 
		A.remove(c)
		if A.isEmpty() then processSolution(S,n) 
		permutations(A,n,S,i+1)
		A.insert(c)	

per l'i-esima permutazione, prova ad implementarlo e stampare; vedrai come è l'ordine delle permutazioni e da lì capirai come modificare ad-hoc lo pseudo-codice, se no devi comprenderne il funzionamente prima..

PS: il link non funziona.

[onlyReferee]

Ciao toni00c!
Tempo fa in un programma di calcolo combinatorio che avevo realizzato ho messo a punto (senza guardare da nessuna parte ) anche una procedura che fa al caso tuo. Il codice è scritto in Visual Basic ma lo su può riadattare tranquillamente in qualsivoglia altro linguaggio. Eccolo:

Private Sub GetPermutazioni(ByRef a() As String, ByRef c() As String, intDim As Integer)
    Dim strTmp As String
    
    If UBound(a) = 1 Then
        c(UBound(c)) = a(1)
        strTmp = ""
        For v = 1 To UBound(c)
            strTmp = strTmp & c(v)
        Next v
        'Ora puoi stampare la permutazione corrente, contenuta nella stringa "strTmp"
    Else
        For i = 1 To UBound(a)
            Dim b() As String
            ReDim b(UBound(a) - 1)
            For j = 1 To UBound(a)
                If j < i Then
                    b(j) = a(j)
                Else
                    If j > i Then
                        b(j - 1) = a(j)
                    End If
                End If
            Next j
            If (intDim = UBound(c) + 1) Then intDim = 1
            c(intDim) = a(i)
            Call GetPermutazioni(b, c, intDim + 1)
        Next i
    End If
End Sub

In $a$ gli passi la stringa contenente il tuo testo iniziale, $c$ non è altro che un vettore di appoggio utilizzato dalla procedura (ricorsiva) inizialmente vuoto della stessa dimensione di $a$ ed $\text{intDim}$ una variabile intera utilizzata per scorrere il vettore (inizialmente va passato semplicemente il valore $1$ al momento della chiamata). Se vuoi utilizzare un array basta che riadatti un attimo il codice. Questo procedura è molto generica e permette di lavorare appunto in genere con stringhe/array di qualunque tipo e pertanto anche con gli array di bit.
Spero di esserti stato d'aiuto.

[vict85]

Ci sono \(n!\) permutazioni diverse di ordine n. Da matematico il problema è che non esiste un unico ordine con cui posso numerare la permutazione. Trovato un certo ordinamento completo puoi, d'altra parte, trovare la i-esima permutazione. Ma il punto è che devi prima definire un ordine.