标准 ML 排列
我正在研究一个列表中所有值的排列函数。
这是我到目前为止所得到的:
//MY ROTATE FUNCTION
fun rotate e [] = [[e]]
| rotate e (x::xs)= (e::x::xs)::(List.map (fn l => x::l) (rotate e xs));
//MY CURRENT PERMUTATION FUNCTION
fun perm [] = []
| perm (x::xs) = List.concat(List.map (fn l => (rotate x xs)) xs) @ perm xs;
输出:
- perm [1,2,3];
val it = [[1,2,3],[2,1,3],[2,3,1],[1,2,3],[2,1,3],[2,3,1],[2,3],[3,2]]
输出应该类似于 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [ 3, 1, 2], [3, 2, 1]]。正如你所看到的,我在这里遗漏了一些东西。我相信问题是我的 3 没有被传递给旋转,因为旋转 3 [1,2] 是我的代码中缺少的,并且由于某种原因在这里有两个 2 元素列表。
如何更正我的 perm 函数以正确显示输出?任何帮助,无论大小,都会对我有很大帮助。
I am working on a function to the permutations for all values in a list.
Here is what I have so far:
//MY ROTATE FUNCTION
fun rotate e [] = [[e]]
| rotate e (x::xs)= (e::x::xs)::(List.map (fn l => x::l) (rotate e xs));
//MY CURRENT PERMUTATION FUNCTION
fun perm [] = []
| perm (x::xs) = List.concat(List.map (fn l => (rotate x xs)) xs) @ perm xs;
OUTPUT:
- perm [1,2,3];
val it = [[1,2,3],[2,1,3],[2,3,1],[1,2,3],[2,1,3],[2,3,1],[2,3],[3,2]]
The output should be something like [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. As you can see I am missing something here. I believe the issue is my 3 is not being passed to rotate as rotate 3 [1,2] is what I am missing from my code along with two 2 element lists being here for some reason.
How can I correct my perm function to show the output correctly? Any help no matter how big or small would help me a lot.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
这是针对您尝试的解决方案的简单修复。你就快到了。
Here is a simple fix for your attempted solution. You were nearly there.
我认为轮换方法不是您想要采用的方法。相反,正如 Shivindap 在此描述 ,执行此类操作的一个好方法是从参数列表中提取第一个元素,并将其附加到尾部的所有排列中。对列表中的每个元素冲洗并重复此操作,您最终将得到所有排列。
您可以在此处找到此方法的深入说明。对于 ML 中的代码示例,您还可以 看看这个。
祝你好运!
I don't think that the rotate approach is the one you'll want to take. Rather, as Shivindap describes here, a good way to do this sort of this is to pull the first element from the argument list, and append it to all permutations of the tail. Rinse and repeat this for every element of the list, and you'll end up with all the permutations.
You'll find an in depth explanation of this approach here. For code samples in ML, you could also check this out.
Best of luck to you!