fork download
copy 
  1. import itertools
  2.  
  3. def find_smallest_covering_subsets(tables, target_numbers_list):
  4.     """
  5.     Determines the smallest subset(s) of tables that contain all specified numbers.
  6.  
  7.     Args:
  8.         tables (dict): A dictionary where keys are table names (e.g., "IMAGE1")
  9.                        and values are the 2D list representations of the tables.
  10.         target_numbers_list (list): A list of numbers that the subset must contain.
  11.  
  12.     Returns:
  13.         list: A list of tuples, where each tuple represents one of the smallest
  14.               subsets of table names that covers all target numbers. Returns an
  15.               empty list if no subset can cover all numbers.
  16.     """
  17.     target_numbers_set = set(target_numbers_list)
  18.  
  19.     # Step 1: Pre-process to find which target numbers each table contains.
  20.     # We create a set of all unique, non-zero numbers for each table.
  21.     table_contents = {}
  22.     for name, table_data in tables.items():
  23.         # Flatten the 2D list into a 1D list and convert to a set
  24.         # The number 0 is treated as a placeholder and ignored.
  25.         unique_numbers = {num for row in table_data for num in row if num != 0}
  26.         table_contents[name] = unique_numbers
  27.  
  28.     # Find the coverage of target numbers for each table
  29.     table_coverage = {}
  30.     for name, numbers in table_contents.items():
  31.         table_coverage[name] = numbers.intersection(target_numbers_set)
  32.  
  33.     # Step 2: Iterate through subset sizes from 1 up to the total number of tables.
  34.     # We stop as soon as we find the first set of solutions, ensuring they are the smallest.
  35.     table_names = list(tables.keys())
  36.     for size in range(1, len(table_names) + 1):
  37.         smallest_subsets = []
  38.         # Generate all combinations of tables for the current size
  39.         for subset_candidate in itertools.combinations(table_names, size):
  40.  
  41.             # Step 3: Check if the current combination covers all target numbers.
  42.             combined_coverage = set()
  43.             for table_name in subset_candidate:
  44.                 combined_coverage.update(table_coverage[table_name])
  45.  
  46.             # If the union of numbers in the subset matches the target set, it's a solution.
  47.             if combined_coverage == target_numbers_set:
  48.                 smallest_subsets.append(subset_candidate)
  49.  
  50.         # If we found any solutions at this size, they must be the smallest.
  51.         # Return them and do not check larger subset sizes.
  52.         if smallest_subsets:
  53.             return smallest_subsets
  54.  
  55.     # If the loop completes without finding a solution, return an empty list.
  56.     return []
  57.  
  58. # --- Data Definition ---
  59.  
  60. IMAGE1 = [
  61.     [ 1,  0,  0, 56,  0, 29, 44,  0],
  62.     [31,  0,  0, 42,  0,  3, 54,  0],
  63.     [ 0,  8, 49,  0, 28,  0,  0, 45],
  64.     [ 0, 26, 47,  0,  6,  0,  0, 51],
  65.     [ 0, 37, 20,  0, 57,  0,  0, 16],
  66.     [ 0, 59, 14,  0, 39,  0,  0, 18],
  67.     [36,  0,  0, 21,  0, 64,  9,  0],
  68.     [62,  0,  0, 11,  0, 34, 23,  0]
  69. ]
  70.  
  71. IMAGE2 = [
  72.     [49, 15,  0,  0, 20, 46,  0,  0],
  73.     [ 0,  0,  2, 64,  0,  0, 35, 29],
  74.     [ 0,  0, 39, 25,  0,  0,  6, 60],
  75.     [24, 42,  0,  0, 53, 11,  0,  0],
  76.     [45, 19,  0,  0, 16, 50,  0,  0],
  77.     [ 0,  0, 30, 36,  0,  0, 63,  1],
  78.     [ 0,  0, 59,  5,  0,  0, 26, 40],
  79.     [12, 54,  0,  0, 41, 23,  0,  0]
  80. ]
  81.  
  82. IMAGE3 = [
  83.     [10,  0, 47,  0,  0, 50,  0, 23],
  84.     [ 0, 32,  0, 57, 40,  0,  1,  0],
  85.     [54,  0, 19,  0,  0, 14,  0, 43],
  86.     [ 0, 36,  0,  5, 28,  0, 61,  0],
  87.     [15,  0, 42,  0,  0, 55,  0, 18],
  88.     [ 0, 25,  0, 64, 33,  0,  8,  0],
  89.     [51,  0, 22,  0,  0, 11,  0, 46],
  90.     [ 0, 37,  0,  4, 29,  0, 60,  0]
  91. ]
  92.  
  93. IMAGE4 = [
  94.     [ 1, 32,  0,  0,  0,  0, 49, 48],
  95.     [56, 41,  0,  0,  0,  0,  8, 25],
  96.     [ 0,  0,  4, 29, 52, 45,  0,  0],
  97.     [ 0,  0, 53, 44,  5, 28,  0,  0],
  98.     [16, 17,  0,  0,  0,  0, 64, 33],
  99.     [57, 40,  0,  0,  0,  0,  9, 24],
  100.     [ 0,  0, 13, 20, 61, 36,  0,  0],
  101.     [ 0,  0, 60, 37, 12, 21,  0,  0]
  102. ]
  103.  
  104. IMAGE5 = [
  105.     [ 7,  0, 61,  0, 34,  0, 28,  0],
  106.     [ 0,  1,  0, 59,  0, 40,  0, 30],
  107.     [42,  0, 20,  0, 15,  0, 53,  0],
  108.     [ 0, 48,  0, 22,  0,  9,  0, 51],
  109.     [ 0, 25,  0, 35,  0, 64,  0,  6],
  110.     [31,  0, 37,  0, 58,  0,  4,  0],
  111.     [ 0, 56,  0, 14,  0, 17,  0, 43],
  112.     [50,  0, 12,  0, 23,  0, 45,  0]
  113. ]
  114.  
  115. IMAGE6 = [
  116.     [16,  0,  0, 37, 20,  0,  0, 57],
  117.     [51,  0,  0, 26, 47,  0,  0,  6],
  118.     [13,  0,  0, 40, 17,  0,  0, 60],
  119.     [50,  0,  0, 27, 46,  0,  0,  7],
  120.     [ 0,  0,  0,  0,  0,  0,  0,  0],
  121.     [ 0,  0,  0,  0,  0,  0,  0,  0],
  122.     [ 0,  0,  0,  0,  0,  0,  0,  0],
  123.     [ 0,  0,  0,  0,  0,  0,  0,  0]
  124. ]
  125.  
  126. # --- Main Execution ---
  127.  
  128. if __name__ == "__main__":
  129.     # The dictionary of all tables
  130.     all_tables = {
  131.         "IMAGE1": IMAGE1,
  132.         "IMAGE2": IMAGE2,
  133.         "IMAGE3": IMAGE3,
  134.         "IMAGE4": IMAGE4,
  135.         "IMAGE5": IMAGE5,
  136.         "IMAGE6": IMAGE6,
  137.     }
  138.  
  139.     # The sequence of numbers to be found
  140.     target_sequence = [18, 7, 9, 16, 20, 5, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 2, 23, 13, 12, 24, 25]
  141.  
  142.     # Find and print the results
  143.     solutions = find_smallest_covering_subsets(all_tables, target_sequence)
  144.  
  145.     if solutions:
  146.         min_size = len(solutions[0])
  147.         print(f"The smallest subset size required to find all numbers is: {min_size}\n")
  148.         print("The following subset(s) of tables contain all the numbers:")
  149.         for i, subset in enumerate(solutions, 1):
  150.             print(f"  Solution {i}: {', '.join(subset)}")
  151.     else:
  152.         print("No subset of the given tables contains all the required numbers.")
  153.  
  154.  
Success #stdin #stdout 0.1s 14204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The smallest subset size required to find all numbers is: 4

The following subset(s) of tables contain all the numbers:
  Solution 1: IMAGE1, IMAGE2, IMAGE3, IMAGE6
https://ideone.com/pdlamw
language:
Python 3 (python  3.12)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!