"""Count missing subpermutations and validate a Sequence Covering Array (SCA).
Usage: python3 validate_sca.py "N12k36v36^36t3.sca"
Only the Python standard library is required. Evaluation is exhaustive and can
be very expensive: its running time grows as binomial(k, t) * N * k.
"""
import itertools
import math
import os
import sys
def test_sca(matrix, k, t):
"""Return the total number of missing subpermutations.
For each t-element subset x of the k symbols, extract the relative order
of its symbols from every row. Store the resulting subpermutations in a
set R to remove duplicates. The number missing for x is t! - len(R).
Sum these counts over all subsets. The value k is a wildcard, not a symbol.
Input rows must contain no repeated non-wildcard symbols.
"""
r = 0
target_count = math.factorial(t)
# Iterate over all t-element subsets of the k available symbols.
for x in itertools.combinations(range(k), t):
x_set = set(x)
R = set()
# Extract each row's subpermutation, preserving the relative order.
for row in matrix:
# Exclude the wildcard k and symbols outside the current subset.
f = tuple(val for val in row if val != k and val in x_set)
if len(f) == t:
R.add(f)
# Accumulate the missing subpermutations for the current subset.
r += target_count - len(R)
return r
def validate_sca_from_file(file_path):
"""Read an SCA file, check its format, and report its coverage.
Extract N, k, and t from the first non-comment, non-empty line. Comment
lines start with C or c and are ignored in memory, never deleted from the
original file. Symbols are numbered from 0 to k - 1; k is a wildcard.
Return True for a valid SCA and False for missing coverage or invalid input.
"""
if not os.path.isfile(file_path):
print(f"Error: The file '{file_path}' does not exist or is not a regular file.")
return False
try:
# utf-8-sig also accepts a UTF-8 byte order mark at the start of a file.
with open(file_path, "r", encoding="utf-8-sig") as file:
valid_lines = [
line.strip() for line in file
if line.strip() and not line.lstrip().lower().startswith("c")
]
except (OSError, UnicodeError) as error:
print(f"Error: Could not read '{file_path}': {error}")
return False
if not valid_lines:
print("Error: The file is empty or contains only comments.")
return False
# Accept 'N k k^k t' or the compact header 'N k t'.
header = valid_lines[0].split()
if len(header) not in (3, 4):
print("Error: Expected a header such as '6 4 4^4 3' (N k k^k t).")
return False
try:
N = int(header[0])
k = int(header[1])
t = int(header[-1]) # The interaction strength is the last header value.
except ValueError:
print("Error: N, k, and t must be integers.")
return False
if N < 1 or k < 1 or not 1 <= t <= k:
print("Error: Expected N >= 1, k >= 1, and 1 <= t <= k.")
return False
if len(header) == 4 and header[2] != f"{k}^{k}":
print(f"Error: Expected '{k}^{k}' as the third header value.")
return False
try:
matrix = [list(map(int, line.split())) for line in valid_lines[1:]]
except ValueError:
print("Error: Matrix entries must be integers.")
return False
if len(matrix) != N:
print(f"Error: Row count mismatch: expected N={N}; found {len(matrix)}.")
return False
# Reject malformed rows instead of incorrectly reporting valid coverage.
for index, row in enumerate(matrix, start=1):
if len(row) != k:
print(f"Error: The length of row {index} is {len(row)}; expected k={k}.")
return False
if any(val < 0 or val > k for val in row):
print(f"Error: Row {index} contains a value outside the range 0 to {k}.")
return False
symbols = [val for val in row if val != k]
if len(symbols) != len(set(symbols)):
print(f"Error: Row {index} contains repeated non-wildcard symbols.")
return False
missing_count = test_sca(matrix, k, t)
filename = os.path.basename(file_path)
if missing_count == 0:
print(f"OK {missing_count} {filename} is an SCA.")
return True
print(f"NOK {missing_count} {filename} is a quasi-SCA (coverage is incomplete).")
return False
if __name__ == "__main__":
# An optional argument selects the input file; otherwise, use the example.
file_path = sys.argv[1] if len(sys.argv) > 1 else "N12k36v36^36t3.sca"
sys.exit(0 if validate_sca_from_file(file_path) else 1)