数组的一个排列算法问题,小鱼纠结了^求助 - Project1

为true时，就行了

上面的算法没用到剪枝

我刚才突发奇想，是不是可以用到图来解决或者dp,
LZ可以用图来想一下

作者: 幻の飞鱼 时间: 2008-3-30 05:51
刚头晕去吃夜宵了，我来思考下

作者: 美兽 时间: 2008-3-30 06:56
没测试，可能会有问题，但思路很清晰，回溯法。

@test = [[6,7,8,5],[2,3,5],[5,7,9,8,7]]

def get_new_arg(arg)
@max = arg.size - 1
@max_h = arg.last.size
@arg = arg
@w = -1
@new_arg = Array.new

find_list([], 0)

return @new_arg
end

def find_list(list, index)
@h = 0
@test[index].each{|a|
      if index == @max
         @new_arg << (list + [a])
         @h += 1
         if @h == @max_h
            return
         end
      else
         l = (list + [a]).clone
         find_list(l, index + 1)
      end
}
end

p get_new_arg(@test)

[LINE]1,#dddddd[/LINE]系统信息：本贴由楼主认可为正确答案，66RPG感谢您的热情解答～

作者: 幻の飞鱼 时间: 2008-3-30 07:02

以下引用美兽于2008-3-29 22:56:49的发言：

没测试，可能会有问题，但思路很清晰，回溯法。

@test = [[6,7,8,5],[2,3,5],[5,7,9,8,7]]

def get_new_arg(arg)
@max = @test.size - 1
@max_h = @test.last.size
@arg = arg
@w = -1
@new_arg = Array.new

find_list([], 0)

return @new_arg
end

def find_list(list, index)
@h = 0
@test[index].each{|a|
   if index == @max
      @new_arg << (list + [a])
      @h += 1
      if @h == @max_h
         return
      end
   else
      l = (list + [a]).clone
      find_list(l, index + 1)
   end
}
end

p get_new_arg(@test)

简单的测试下没问题，不过超级没看懂……
仔细研究研究

作者: 美兽 时间: 2008-3-30 07:02

简单的测试下没问题，不过超级没看懂……
仔细研究研究

从后至前，逆循环。

至于如何提出size == 1的组合，就不用赘述了吧。

作者: 沉影不器 时间: 2008-3-30 07:06
提示: 作者被禁止或删除内容自动屏蔽

作者: 幻の飞鱼 时间: 2008-3-30 07:08
其实 << 的功能不是很懂

作者: 美兽 时间: 2008-3-30 07:11

以下引用幻の飞鱼于2008-3-29 23:08:03的发言：

其实 << 的功能不是很懂

[本贴由作者于 2008-3-29 23:09:23 最后编辑]

呵呵，确实那里漏了，<<是Array的方法，与Integer移位运算<<方法性质不同，尽管RUBY几乎完全面向对象。

作者: 幻の飞鱼 时间: 2008-3-30 07:19

<< 和直接用 = 的区别在哪？？=。=

测试了几次没找出关键

作者: 美兽 时间: 2008-3-30 10:27

以下引用幻の飞鱼于2008-3-29 23:19:35的发言：

<< 和直接用 = 的区别在哪？？=。=

测试了几次没找出关键

<<对于Array对象来说类似于push,顺路美化代码

@test = [[6,7,8,5],[2,3,5],[5,7,9,8,7]]

def get_new_arg(arg)
@arg = arg
@max = @arg.size - 1
@max_h = @arg.last.size - 1
@new_arg = Array.new

find_list([], 0)

return @new_arg
end

def find_list(list, index)
@h = 0
@arg[index].each{|a|
   if index == @max
      @new_arg << (list + [a])
      @h += 1
      return if @h > @max_h
   end
   find_list(list + [a], index + 1)
}
end

p get_new_arg(@test)

作者: 沉影不器 时间: 2008-3-30 18:41
提示: 作者被禁止或删除内容自动屏蔽

作者: 美兽 时间: 2008-4-1 04:28
翻老帖,实际那个美化有问题— —
each本身即是遍历，@h也是多余。

终稿：

@test = [[6,7,8,5],[2,3,5],[5,7,9,8,7]]

def get_new_arg(arg)
@arg = arg
@max = @arg.size - 1
@new_arg = Array.new

find_list([], 0)

return @new_arg
end

def find_list(list, index)
@arg[index].each{|a|
      if index == @max
         @new_arg << (list + [a])
         next
      end
      find_list(list + [a], index + 1)
}
end

p get_new_arg(@test)

作者: 幻の飞鱼 时间: 2008-4-1 05:38
的确，EACH遍厉害后会自动结束
这次是……简化了

作者: bloblo 时间: 2008-4-1 09:23
好贴啊不错啊谢谢楼主分享拉 (*^__^*) 嘻嘻……








------------------------------------------------------------
域名注册就是网址，网址也叫中文域名，搞不懂！头晕～

作者: dna_7086 时间: 2008-7-4 09:33
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Project1 (https://rpg.blue/)