Calcola tutte le permutazioni di una stringa in Swift

Question

Per la stringa "ABC", lo snippet di codice seguente calcola 5 delle 6 permute totali. La mia strategia era quella di inserire ogni carattere in ogni indice possibile indice. Ma la funzione non ottiene mai "CBA" come una possibile permutazione. Cosa mi manca?

var permutationArray:[String] = []; 
let string: String = "ABC" 

func permute(input: String) -> Array<String> 
{ 
    var permutations: Array<String> = [] 

    /* Convert the input string into characters  */ 
    var inputArray: Array<String> 
    inputArray = input.characters.map { String($0) } 
    print(inputArray) 

    /* For each character in the input string...  */ 
    for var i = 0; i < inputArray.count; i++ 
    { 

     /*  Insert it at every index    */ 
     let characterInArray: String = inputArray[i] 
     var inputArrayCopy: Array<String> = [] 
     for var y = 0; y < inputArray.count; y++ 
     { 

      inputArrayCopy = inputArray 
      inputArrayCopy.removeAtIndex(i) 
      inputArrayCopy.insert(characterInArray, atIndex:y) 

      let joiner = "" 
      let permutation = inputArrayCopy.joinWithSeparator(joiner) 
      if !permutations.contains(permutation) { 
       permutations.insert(permutation, atIndex: 0) 
      } 
     } 
    } 

    return permutations 
} 

var permutations = permute(string) 
print(permutations) 

Answer 1

func generate(n: Int, var a: [String]){ 
    if n == 1 { 
     print(a.joinWithSeparator("")) 
    } else { 
     for var i = 0; i < n - 1; i++ { 
      generate(n - 1, a: a) 
      if n % 2 == 0 { 
       let temp = a[i] 
       a[i] = a[n-1] 
       a[n-1] = temp 
      } 
      else { 
       let temp = a[0] 
       a[0] = a[n-1] 
       a[n-1] = temp 
      } 
     } 
     generate(n - 1, a: a) 
    } 
} 


func testExample() { 
    var str = "123456" 
    var strArray = str.characters.map { String($0) } 
    generate(str.characters.count, a: strArray) 
} 

Non reinventare la ruota. Ecco una semplice porta di Heap's algorithm.

Answer 2

Ecco un'espressione dell'algoritmo di Heap (Sedgewick?) In Swift. È efficiente perché la matrice viene passata per riferimento anziché essere passata per valore (anche se ovviamente ciò significa che si deve essere pronti a manomettere l'array). Swapping è espressa in modo efficiente attraverso l'uso del built-in swapAt(_:_:) funzione:

func permutations(_ n:Int, _ a: inout Array<Character>) { 
    if n == 1 {print(a); return} 
    for i in 0..<n-1 { 
     permutations(n-1,&a) 
     a.swapAt(n-1, (n%2 == 1) ? 0 : i) 
    } 
    permutations(n-1,&a) 
} 

Proviamo:

var arr = Array("ABC".characters) 
permutations(arr.count,&arr) 

uscita:

["A", "B", "C"] 
["B", "A", "C"] 
["C", "A", "B"] 
["A", "C", "B"] 
["B", "C", "A"] 
["C", "B", "A"] 

Se ciò che si voleva fare con ogni la permutazione non era semplicemente quella di stamparlo, sostituire print(a) con qualcos'altro. Ad esempio, è possibile aggiungere ogni permutazione a un array, combinare l'array di caratteri in una stringa, qualunque sia.

Answer 3

Mentre Stefan e Matt fanno un buon punto sull'utilizzo dell'algoritmo di Heap, penso che tu abbia una domanda importante sul perché il codice non funziona e come si farebbe a eseguire il debug del codice.

In questo caso, l'algoritmo è semplicemente errato e il modo migliore per scoprire che è con carta e matita IMO. Quello che stai facendo è scegliere ogni elemento, rimuoverlo dall'array e poi iniettarlo in ogni possibile posizione. Il tuo codice fa ciò che hai chiesto di fare. Ma non è possibile arrivare a "CBA" in questo modo. Stai spostando solo un elemento alla volta, ma "CBA" ha due elementi fuori servizio. Se si espande a ABCD, si troveranno molte più permutazioni mancanti (genera solo 10 dei 24).

Mentre l'algoritmo di Heap è ben efficiente, il punto più profondo è che percorre l'intero array e scambia ogni coppia possibile, invece di spostare un singolo elemento attraverso l'array. Qualsiasi algoritmo scelto deve avere quella proprietà.

E proprio per gettare il cappello sul ring, mi piacerebbe espandere sull'attuazione di Matt in questo modo:

// Takes any collection of T and returns an array of permutations 
func permute<C: Collection>(items: C) -> [[C.Iterator.Element]] { 
    var scratch = Array(items) // This is a scratch space for Heap's algorithm 
    var result: [[C.Iterator.Element]] = [] // This will accumulate our result 

    // Heap's algorithm 
    func heap(_ n: Int) { 
     if n == 1 { 
      result.append(scratch) 
      return 
     } 

     for i in 0..<n-1 { 
      heap(n-1) 
      let j = (n%2 == 1) ? 0 : i 
      scratch.swapAt(j, n-1) 
     } 
     heap(n-1) 
    } 

    // Let's get started 
    heap(scratch.count) 

    // And return the result we built up 
    return result 
} 

// We could make an overload for permute() that handles strings if we wanted 
// But it's often good to be very explicit with strings, and make it clear 
// that we're permuting Characters rather than something else. 

let string = "ABCD" 
let perms = permute(string.characters) // Get the character permutations 
let permStrings = perms.map() { String($0) } // Turn them back into strings 
print(permStrings) // output if you like 

Answer 4

Ecco la mia soluzione.

È possibile copiarlo/incollarlo in un file ed eseguirlo con la riga di comando swift binary.

Per una permutazione di 7 tutti i caratteri univoci, questo algoritmo richiede circa 0,06 secondi per l'esecuzione.