weixin_47261246 2020-06-13 15:19 采纳率: 12.5%
浏览 110
已结题

给定从1到N,N个整数,每个整数给两次,求出2N个元素的所有组合,满足以下条件:1.从1-N的每个整数必须出现两次2.同一整数之间的距离就是该整数的值?

用python实现以下程序
给定从1到N,N个整数,每个整数给两次,求出2N个元素的所有组合,满足以下条件:
1.从1-N的每个整数必须出现两次
2.同一整数之间的距离就是该整数的值。
问题如下
1.设计状态空间树,描述想法和思路,通过回溯来解决这个问题、
2.在Python中以函数的形式实现该算法:
def twice_distance(n):

本人画了多次tree,但是不是时间复杂度太高就是一直输出的不是最终答案
图片说明

  • 写回答

2条回答 默认 最新

  • dabocaiqq 2020-06-14 07:28
    关注
    评论
  • u010146791 2020-06-15 18:27
    关注

    从左往右每个格子依次放每个数 (注意到放了一个数以后第二次出现一定在右边 且位置确定)。 放不下去了就回溯。

    状态空间就是放满的前缀

    def twice_distance(n):
      init = [0 for i in range(2*n)]
      return find_all(n, init, 0, set())
    
    def find_all(n, arr, next_pos, selected):
      while next_pos < len(arr) and arr[next_pos] != 0:
        next_pos += 1
    
      if next_pos == len(arr):
        return [arr.copy()]
    
      ans = []
      for i in range(1, n+1):
        other_pos = next_pos + i + 1
        if not i in selected and other_pos < len(arr) and arr[other_pos] == 0:
          arr[next_pos] = i
          arr[other_pos] = i
          selected.add(i)
          ans += find_all(n, arr, next_pos+1, selected)
          selected.remove(i)
          arr[next_pos] = 0
          arr[other_pos] = 0
      return ans 
    
    print(twice_distance(4))
    # [[2, 3, 4, 2, 1, 3, 1, 4], [4, 1, 3, 1, 2, 4, 3, 2]]
    

    如果太慢再考虑优化一下

    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 VINS-Mono或Fusion中feature_manager中estimated_depth是特征的深度还是逆深度?
  • ¥15 谷歌浏览器如何备份抖音网页数据
  • ¥15 分别有什么商家下面需要非常多的骑手为它工作?
  • ¥15 开机logo到Qt应用起来会黑屏将近两秒时间
  • ¥15 vfp工程项目管理系统的业务流程图
  • ¥50 找佬协助我完成Cpp课题(大一)
  • ¥30 音频相似性匹配案例收集
  • ¥15 PHP导入CSV表的时候超过两千行数据出现的模块不存在问题
  • ¥20 U盘安装操作系统后会导致内存下降,以前的文件都消失吗?
  • ¥15 ESP32-CAM连续拍照一段时间后就会报错
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部