在sml中實現next_permutation？

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) = ... 

您還可以檢查k和STR的長度一樣

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

作爲內部循環函數，它會以糟糕的方式工作，所以它更好地做別的事情，但這是 它涉及String的表示形式。如果你想交換字符，它會在最壞情況下工作O（n），其中n - 字符串的長度（因爲你需要刪除它們之間的字符，然後把它們放回去）。所以一般來說，你需要使用O（n^2）時間，這是非常無效的。