0

0

在排列上应用处理程序,而不需要级别缓存?

WBOY

WBOY

发布时间:2024-02-06 09:42:08

|

834人浏览过

|

来源于stackoverflow

转载

在排列上应用处理程序,而不需要级别缓存?

问题内容

我想编写一个函数,将给定的处理程序应用于所有输入排列,而不返回整个排列。

代码

(在 go 中)

  • 查找排列:

    // apply given handler on each combination, and return count only,
    func findallpermutationapplyhandler[t any](ts []t, handler func([]t)) int {
        n := 0
        comblist := [][]t{{}} // when empty input, has 1 empty combination, not 0 combination,
        for i := len(ts) - 1; i >= 0; i-- {
            islastlevel := false
            if i == 0 {
                islastlevel = true
            }
    
            // prefix := ts[0:i]
            mover := ts[i]
            // fmt.printf("\nprefix = %v, mover = %v:\n", prefix, mover)
            var comblist2 [][]t // combinations with an extra item added,
            for _, comb := range comblist {
                for j := 0; j <= len(comb); j++ { // insert mover at index j of comb,
                    comb2 := append(append(append([]t{}, comb[0:j]...), mover), comb[j:]...) // new_empty + left + mover + right
                    if islastlevel {
                        n++
                        handler(comb2)
                    } else {
                        comblist2 = append(comblist2, comb2)
                    }
                }
            }
    
            comblist = comblist2
        }
    
        return n
    }
  • 测试用例(简单)

    影缘版商城
    影缘版商城

    率先引入语言包机制,可在1小时内制作出任何语言版本,程序所有应用文字皆引自LANG目录下的语言包文件,独特的套图更换功能,三级物品分类,购物车帖心设计,在国内率先将购物车与商品显示页面完美结合,完善的商品管理,具备上架、下架缺货及特价商品设置功能多多,商城名、消费税、最低购物金额、货币符号、商城货币名称全部后台设定,多级用户考虑,管理员只需要设置用户级别、不同级别用户之返点系统自动判断用户应得返还

    下载
    func TestFindAllPermutationApplyHandler(t *testing.T) {
        assert.Equal(t, FindAllPermutationApplyHandler([]int{1, 2, 3}, func(comb []int) {
            fmt.Printf("\t%v\n", comb)
        }), 6)
    }

说明

  • 上面的函数 findallpermutationapplyhandler() 可以查找排列,并将给定的处理程序应用于每个组合。
  • 但是它需要缓存之前的 n-1 级别(同时最近的 2 个级别)
  • 我已经避免了最终级别的缓存,因为没有更多级别依赖于它。

问题

    1. 是否可以避免缓存最近2个级别?

      (又名,使空间复杂度为 o(1)o(n),甚至我猜 o(n^2) 更好)。

    1. 但这对我来说似乎不可能,因为级别 i 是基于级别 i-1 的,对吧?
    1. 如果是的话,是否有更好的算法来降低空间复杂度?迭代是首选(而不是递归)。

正确答案


听起来您正在寻找Pandita 算法

这是一种按字典顺序迭代生成数组所有排列的简单方法。

但是,它要求您可以对数组的元素进行排序。如果不能(因为它们是泛型类型),那么您可以创建所有数组索引的辅助数组,并生成其排列。

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

405

2023.08.14

c++ 根号
c++ 根号

本专题整合了c++根号相关教程,阅读专题下面的文章了解更多详细内容。

25

2026.01.23

c++空格相关教程合集
c++空格相关教程合集

本专题整合了c++空格相关教程,阅读专题下面的文章了解更多详细内容。

31

2026.01.23

yy漫画官方登录入口地址合集
yy漫画官方登录入口地址合集

本专题整合了yy漫画入口相关合集,阅读专题下面的文章了解更多详细内容。

119

2026.01.23

漫蛙最新入口地址汇总2026
漫蛙最新入口地址汇总2026

本专题整合了漫蛙最新入口地址大全,阅读专题下面的文章了解更多详细内容。

180

2026.01.23

C++ 高级模板编程与元编程
C++ 高级模板编程与元编程

本专题深入讲解 C++ 中的高级模板编程与元编程技术,涵盖模板特化、SFINAE、模板递归、类型萃取、编译时常量与计算、C++17 的折叠表达式与变长模板参数等。通过多个实际示例,帮助开发者掌握 如何利用 C++ 模板机制编写高效、可扩展的通用代码,并提升代码的灵活性与性能。

16

2026.01.23

php远程文件教程合集
php远程文件教程合集

本专题整合了php远程文件相关教程,阅读专题下面的文章了解更多详细内容。

70

2026.01.22

PHP后端开发相关内容汇总
PHP后端开发相关内容汇总

本专题整合了PHP后端开发相关内容,阅读专题下面的文章了解更多详细内容。

63

2026.01.22

php会话教程合集
php会话教程合集

本专题整合了php会话教程相关合集,阅读专题下面的文章了解更多详细内容。

64

2026.01.22

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

相关下载

更多

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Excel 教程
Excel 教程

共162课时 | 13.3万人学习

Bootstrap 5教程
Bootstrap 5教程

共46课时 | 3万人学习

PHP新手语法线上课程教学
PHP新手语法线上课程教学

共13课时 | 0.9万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号