草庐IT

python - 有没有办法找出A是否是B的子矩阵？

coder 2023-08-25 原文

我加引号是因为我的意思是例如:

B = [[1,2,3,4,5],
     [6,7,8,9,10],
     [11,12,13,14,15],
     [16,17,18,19,20]]

假设我们选择第 2,4 行和第 1,3 列，交叉点将给我们

A = [[6,8],
     [16,18]]

我的问题是假设我有 A 和 B，有没有办法找出从 B 中选择了哪些行和列给 A？

顺便说一下，如果你能用 python/numpy 给出答案就更好了。但仅在数学或其他编程语言中也可以。

最佳答案

这是一个非常困难的组合问题。事实上 Subgraph Isomorphism Problem可以简化为您的问题(如果矩阵 A 只有 0-1 个条目，您的问题就是子图同构问题)。已知此问题是 NP 完全问题。

这是一个递归回溯解决方案，它比暴力破解所有可能的解决方案要好一些。请注意，在最坏的情况下，这仍然需要指数时间。但是，如果您假设存在一个解决方案并且没有歧义(例如，B 中的所有条目都是不同的)，这会在线性时间内找到解决方案。 

def locate_columns(a, b, offset=0):
    """Locate `a` as a sublist of `b`.

    Yields all possible lists of `len(a)` indices such that `a` can be read
    from `b` at those indices.
    """
    if not a:
        yield []
    else:
        positions = (offset + i for (i, e) in enumerate(b[offset:])
                     if e == a[0])
        for position in positions:
            for tail_cols in locate_columns(a[1:], b, position + 1):
                yield [position] + tail_cols


def locate_submatrix(a, b, offset=0, cols=None):
    """Locate `a` as a submatrix of `b`.

    Yields all possible pairs of (row_indices, column_indices) such that
    `a` is the projection of `b` on those indices.
    """
    if not a:
        yield [], cols
    else:
        for j, row in enumerate(b[offset:]):
            if cols:
                if all(e == f for e, f in zip(a[0], [row[c] for c in cols])):
                    for r, c in locate_submatrix(a[1:], b, offset + j + 1, cols):
                        yield [offset + j] + r, c
            else:
                for cols in locate_columns(a[0], row):
                    for r, c in locate_submatrix(a[1:], b, offset + j + 1, cols):
                        yield [offset + j] + r, c

B = [[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20]]
A = [[6,8], [16,18]]

for loc in locate_submatrix(A, B):
    print loc

这将输出:

([1, 3], [0, 2])

关于python - 有没有办法找出A是否是B的子矩阵？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26896687/

找出pythoncodeoffsetsectionalgorithmmathnumpymatrix

有关python - 有没有办法找出A是否是B的子矩阵？的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  3. ruby - 难道Lua没有和Ruby的method_missing相媲美的东西吗？ - 2

    我好像记得Lua有类似Ruby的method_missing的东西。还是我记错了？ 最佳答案 表的metatable的__index和__newindex可以用于与Ruby的method_missing相同的效果。 关于ruby-难道Lua没有和Ruby的method_missing相媲美的东西吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7732154/

  4. ruby-on-rails - rails 目前在重启后没有安装 - 2

    我有一个奇怪的问题:我在rvm上安装了ruby​​onrails。一切正常，我可以创建项目。但是在我输入“railsnew”时重新启动后，我有“程序'rails'当前未安装。”。SystemUbuntu12.04ruby-v"1.9.3p194"gemlistactionmailer(3.2.5)actionpack(3.2.5)activemodel(3.2.5)activerecord(3.2.5)activeresource(3.2.5)activesupport(3.2.5)arel(3.0.2)builder(3.0.0)bundler(1.1.4)coffee-rails(

  5. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  6. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  7. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  8. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  9. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  10. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

随机推荐