Julia - 迭代字典中的键组合 [英] Julia - Iterating over combinations of keys in a dictionary

问题描述

有没有一种很好的方法来迭代字典中的键组合？

Is there a nifty way to iterate over combinations of keys in a dictionary?

我的字典的值如下：

[1] => [1,2], [2,3] => [15], [3] => [6,7,8], [4,9,11] => [3], ... 

我需要做的是获取所有的密钥组合长度 1：n 其中 n 可能是fx 3

what I need to do is fetch all combinations of keys that are of length 1:n where n might be fx 3

所以在上面的例子中，我想迭代

So as in the example above, I would want to iterate over

[[1], [3], [2,3], [[1],[1,2]], [[3],[2,3]], [4,9,11]]

我知道我可以收集密钥，但我的字典相当大，我正在重新设计整个算法，因为它在<$ c $时开始疯狂交换c> n> 3 ，效率极低

I know I could just collect the keys, but my dictionary is rather large and I am in the middle of redesigning the entire algorithm because it starts swapping insanely when n > 3, reducing efficiency terribly

tl; dr 有没有办法从字典中创建组合迭代器收集 - 字典？

tl;dr is there a way to create a combinatoric iterator from a dictionary without collect-ing the dictionary?

推荐答案

以下是直截了当实现，试图通过字典最小化一点。此外，它使用OrderedDict，因此保持关键索引是有意义的（因为Dicts不承诺每次都进行一致的密钥迭代，因此有意义的密钥索引）。

The following is a straight forward implementation, which tries to minimize a bit on going through the dictionary. Additionally it uses OrderedDict so holding key indices makes sense (since Dicts don't promise consistent key iteration each time and thus meaningful key indexing).

using Iterators
using DataStructures

od = OrderedDict([1] => [1,2], [2,3] => [15], [3] => [6,7,8], [4,9,11] => [3])

sv = map(length,keys(od))        # store length of keys for quicker calculations
maxmaxlen = sum(sv)              # maximum total elements in good key
for maxlen=1:maxmaxlen           # replace maxmaxlen with lower value if too slow
  @show maxlen
  gsets = Vector{Vector{Int}}()  # hold good sets of key _indices_
  for curlen=1:maxlen
    foreach(x->push!(gsets,x),
     (x for x in subsets(collect(1:n),curlen) if sum(sv[x])==maxlen))
  end
  # indmatrix is necessary to run through keys once in next loop
  indmatrix = zeros(Bool,length(od),length(gsets))
  for i=1:length(gsets)              for e in gsets[i]
      indmatrix[e,i] = true
    end
  end
  # gkeys is the vector of vecotrs of keys i.e. what we wanted to calculate
  gkeys = [Vector{Vector{Int}}() for i=1:length(gsets)]
  for (i,k) in enumerate(keys(od))
    for j=1:length(gsets)
      if indmatrix[i,j]
        push!(gkeys[j],k)
      end
    end
  end
  # do something with each set of good keys
  foreach(x->println(x),gkeys)
end

这比你现有的更有效吗？将代码放入函数或将其转换为Julia任务也会更好，每次迭代都会生成下一个键集。

Is this more efficient that what you currently have? It would also be better to put the code in a function or turn it into a Julia task which produces the next keys set each iteration.

---更新---

使用 https://stackoverflow.com中有关任务的迭代器的答案/ a / 41074729/3580870

改进的迭代器版本是：

function keysubsets(n,d)
  Task() do
    od = OrderedDict(d)
    sv = map(length,keys(od))        # store length of keys for quicker calculations
    maxmaxlen = sum(sv)              # maximum total elements in good key
    for maxlen=1:min(n,maxmaxlen)    # replace maxmaxlen with lower value if too slow
      gsets = Vector{Vector{Int}}()  # hold good sets of key _indices_
      for curlen=1:maxlen
        foreach(x->push!(gsets,x),(x for x in subsets(collect(1:n),curlen) if sum(sv[x])==maxlen))
      end
      # indmatrix is necessary to run through keys once in next loop
      indmatrix = zeros(Bool,length(od),length(gsets))
      for i=1:length(gsets)              for e in gsets[i]
          indmatrix[e,i] = true
        end
      end
      # gkeys is the vector of vecotrs of keys i.e. what we wanted to calculate
      gkeys = [Vector{Vector{Int}}() for i=1:length(gsets)]
      for (i,k) in enumerate(keys(od))
        for j=1:length(gsets)
          if indmatrix[i,j]
            push!(gkeys[j],k)
          end
        end
      end
      # do something with each set of good keys
      foreach(x->produce(x),gkeys)
    end
  end
end

现在可以通过这种方式迭代所有密钥子集，直到组合大小为4（在运行其他StackOverflow答案的代码之后）：

Which now enables iterating over all keysubsets up to combined size 4 in this way (after running the code from the other StackOverflow answer):

julia> nt2 = NewTask(keysubsets(4,od))
julia> collect(nt2)
10-element Array{Array{Array{Int64,1},1},1}:
 Array{Int64,1}[[1]]          
 Array{Int64,1}[[3]]          
 Array{Int64,1}[[2,3]]        
 Array{Int64,1}[[1],[3]]      
 Array{Int64,1}[[4,9,11]]     
 Array{Int64,1}[[1],[2,3]]    
 Array{Int64,1}[[2,3],[3]]    
 Array{Int64,1}[[1],[4,9,11]] 
 Array{Int64,1}[[3],[4,9,11]] 
 Array{Int64,1}[[1],[2,3],[3]]

（必须从链接的StackOverflow答案定义NewTask）。

(the definition of NewTask from the linked StackOverflow answer is necessary).

这篇关于Julia - 迭代字典中的键组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！