美文网首页
回溯算法 - 全排列算法实现(python&dart)

回溯算法 - 全排列算法实现(python&dart)

作者: yytester | 来源:发表于2021-01-11 16:50 被阅读0次

回溯算法 , 就是 穷举

解决一个回溯问题,实际上就是一个决策树的遍历过程.

  1. 路径: 也就是已经做出的选择
  2. 选择列表: 也就是你当前可以做的选择
  3. 结束条件: 也就是到达决策树底层,无法再做选择的条件.

回溯算法的一个特点: 它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高,不可能低于0(n!),因为穷举整颗决策树是无法避免的.

python代码:

from rich.console import Console
from rich import print

console = Console() 
res  = []

def permute( nums):
    tarck = []
    backtrack(nums,tarck)
    return  res

def backtrack(nums,track):
    if (len(track) == len(nums) ):
        res.append(track.copy())
        console.log( 'nums长度和track长度一致'  , style="bold red underline")
        print('当前res是: '+ str(res))
        return res
 
    for i in nums:
        if i in track:
            continue
        track.append(i)
        
        backtrack(nums,track)
        track.pop()
        
        
res  = permute([1,2,3])     
console.log( res  , style="bold green ")
# 输出结果:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]    

dart代码:


List<List<int>> res = [];

List<List<int>> permute(List<int> nums){
  List<int> track = [] ;
  backtrack(nums, track);
  return res;
}

void backtrack(List<int> nums, List<int> track){

  if (nums.length == track.length){
    res.add(track.sublist(0));
    print("当前res是: "+res.toString());
    return ;
  }

  for(int i=0;i<nums.length;i++){

    if (track.contains(nums[i])){
      continue;
    }

    track.add(nums[i]); 
    backtrack(nums, track);
    track.removeLast();
  }

}

void main() {

  var xx = permute([1,2,3]);
  print(xx);


}


Flutter 写的app, 需要源码可以私信~~

相关文章

  • 回溯算法 - 全排列算法实现(python&dart)

    回溯算法 , 就是 穷举 解决一个回溯问题,实际上就是一个决策树的遍历过程. 路径: 也就是已经做出的选择 选择列...

  • 「回溯算法」专题介绍

    「回溯算法」专题介绍 第 1 节:从全排列问题开始理解回溯搜索算法 引言 大家好,今天要和大家分享的主题是“回溯算...

  • 739. 每日温度/46. 全排列

    739. 每日温度 相关标签 : 哈希表 栈 46. 全排列 相关标签: 回溯算法

  • 全排列与字典序

    全排列 递归实现全排列; 首先来说递归算法实现全排列: 例如,对于{1,2,3,4}的例子进行全排列,其可以分解...

  • 全排列算法

    代码实现 参考资料 全排列算法 - bilibili.com

  • 从全排列看回溯算法

    从全排列看回溯算法 最近又刷起了算法,仿佛回到了大一时奋战到深夜场景,走上社会之初发现大学里学的都是啥玩意儿,工作...

  • 回溯算法解决全排列问题

  • leetcode第46题:全排列 [中等]

    题目描述 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 考点 回溯算法 深度优先搜索 解题思路 回溯算...

  • UIcollectionView实现不规则排列的算法

    UIcollectionView实现不规则排列的算法 UIcollectionView实现不规则排列的算法,简单的...

  • 回溯算法

    回溯算法 回溯算法介绍   回溯算法并不是非常复杂的算法, 很多人接触过但是未必知道这是回溯算法; 典型的回溯算法...

网友评论

      本文标题:回溯算法 - 全排列算法实现(python&dart)

      本文链接:https://www.haomeiwen.com/subject/uuvdaktx.html