在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）时间，这是非常无效的。