用于生成排列的记忆化

发布于 2024-12-21 22:58:44 字数 78 浏览 0 评论 0原文

有没有办法有生成排列的记忆技术。例如 对于数字 1234...

对我来说问题是它占用了大量内存。有什么办法可以占用适量的内存

Is there any way to have memoization technique of generation the permutation. For example
for numbers 1234...

For me the problem is that it is taking a lot of memory. Is there any way to in some moderate amount of memory

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

流年里的时光 2024-12-28 22:58:44

对于任何字符串,假设有 n 个不同的字符,n!存在排列,因此需要的空间会很大。如果您只需要枚举排列,那么我建议不要存储它们,而是在计算每个排列时直接显示每个排列

For any string, say with n distinct characters, n! permutations exist, thus space needed will be large. If you just need to enumerate the permutations, then I would suggest not to store them, but directly display each one as you calculate each one

梦与时光遇 2024-12-28 22:58:44

是的,当然,可以使用记忆化来生成排列(就像几乎任何其他计算一样,当它有意义时)。具体步骤取决于您的排列生成算法。例如,如果您有函数 perms(numbers) ,它接受一组数字(例如 {1, 2, 3, 4})并返回所有排列的集合(这些数字的有序向量,例如 {[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], ...} ) 经过使用数字的子集递归调用perms(),您可以直接记住这个perms()函数。为此,请将缓存创建为映射,其中键是数字集,值是函数调用的结果。

关于你问题的第二部分(关于记忆)。记忆化本质上会使用大量内存。您始终可以通过使用某种固定大小的缓存来修复此数量(例如 LRU/LFU< /a> map),但您应该明白这破坏了记忆概念,并且对 perms() 的某些调用仍将被计算两次或更多次。

Yes, of course, it is possible to use memoization for permutation generation (as almost any other computation, when it makes sense). Concrete steps depend on your permutation generation algorithm. For example, if you have function perms(numbers) that takes set of numbers (say, {1, 2, 3, 4}) and returns set of all permutations (ordered vectors of these numbers, say, {[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], ...}) by recursive calling perms() with subsets of numbers, you can memoize this perms() function directly. To do so, create cache as a map, where keys are sets of numbers and values are results of function call.

Concerning second part of your question (about memory). Memoization by its nature uses large amount of memory. You can always fix this amount by using some kind of fixed-size cache (e.g. LRU/LFU map), but you should understand that this breaks memoization concept, and some calls to perms() will be still computed twice or more times.

清晨说晚安 2024-12-28 22:58:44

如果您想连续生成排列并且不需要同时全部排列,那么您最好按字典顺序迭代它们。编写一个函数 nextPerm ,它接受一个排列并返回字典中的下一个排列订单

If you want to generate the permutations in succession and don't need them all simultaneously, then you may be better off iterating through them lexicographically. Write a function nextPerm that takes in a permutation and returns the next permutation in lexicographic order.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文