Реализация next_permutation в sml?

Question

Как бы это реализовать в SML? Можно ли изменить внутренний цикл for на рекурсивную внутреннюю функцию?

void RecursivePermute(char str[], int k) { 

int j; 

// Base-case: All fixed, so print str. 
if (k == strlen(str)) 
    printf("%s\n", str); 

else { 

    // Try each letter in spot j. 
    for (j=k; j<strlen(str); j++) { 

     // Place next letter in spot k. 
     ExchangeCharacters(str, k, j); 

     // Print all with spot k fixed. 
     RecursivePermute(str, k+1); 

     // Put the old char back. 
     ExchangeCharacters(str, j, k); 
    } 
} 

}

Answer 1

Вы могли бы написать это как

val rec RecursivePermute = fn (str, k) => ... 

или

fun RecursivePermute (str, k) = ... 

Вы также можете проверить к и длину ул как

if (String.size str = k) 
then ... 
else ... 

Как функция внутреннего цикла, это будет работать плохо, поэтому лучше сделать что-то еще, но это Это касается представления строки. Если вы хотите поменять символы, в худшем случае будет работать O (n), где n - длина строки (из-за необходимости удалить символы между ними, а затем вернуть их). Поэтому, как правило, вам нужно использовать время O (n^2), которое весьма неэффективно.