Ramsey's theorem: Difference between revisions

Line 1,046:

'''Adapted from [[#Wren|Wren]]'''

'''Also works with gojq, the Go implementation of jq.

'''Also works with gojq, the Go implementation of jq.'''

With one minor tweak to the line that uses string interpolation, the following also works with jaq, the Rust implementation of jq.

In the following, if a is a connectivity matrix and if $i != $j,

Line 1,054:

Line 1,056:

# Input: {a, idx} where .a is a connectivity matrix and

# .idx is an array with length equal to the size of the group of interest.

# Assuming .idx[0] is 0, then depending on the value of ctype,

# Assuming .idx[0] is 0, then depending on the value of $ctype,

# findGroup(ctype; 1; 1) will either find

# findGroup($ctype; 1; 1) will either find

# a completely connected or a uncompletely unconnected

# group of size `.idx|length` in .a, if it exists, or emit false.

# Set ctype to 0 to find a completely unconnected group.

# Set $ctype to 0 to find a completely unconnected group.

def findGroup(ctype; min; $depth):

def findGroup($ctype; $min; $depth):

. as $in

| (.a|length) as $max

| (.idx|length) as $size

| if $depth == $size

then (if ctype == 0 then "un" else "" end) as $cs

then (if $ctype == 0 then "un" else "" end) as $cs

| "Totally \($cs)connected group: " + (.idx | join(" "))

else .i = min

else .i = $min

| until (.i >= $max or .emit;

.n = 0

| until (.n >= $depth or .a[.idx[.n]][.i] != ctype;

| until (.n >= $depth or .a[.idx[.n]][.i] != $ctype;

.n += 1)

| if .n == $depth

then .idx[.n] = .i

| .emit = findGroup(ctype; 1; $depth+1)

| .emit = findGroup($ctype; 1; $depth+1)

else .

end