Ramsey's theorem: Difference between revisions
m
→{{header|Wren}}: Minor tidy
SqrtNegInf (talk | contribs) m (→{{header|Ruby}}: Fix comment: Perl 6 --> Raku) |
m (→{{header|Wren}}: Minor tidy) |
||
(16 intermediate revisions by 9 users not shown) | |||
Line 6:
A specially-nominated solution may be used, but if so it '''must''' be checked to see if if there are any sub-graphs that are totally connected or totally unconnected.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V a = [[‘0’] * 17] * 17
V idx = [0] * 4
F find_group(mark, min_n, max_n, depth = 1)
I depth == 4
V prefix = I mark == ‘1’ {‘’} E ‘un’
print(‘Fail, found totally #.connected group:’.format(prefix))
L(i) 4
print(:idx[i])
R 1B
L(i) min_n .< max_n
V n = 0
L n < depth
I :a[:idx[n]][i] != mark
L.break
n++
I n == depth
:idx[n] = i
I find_group(mark, 1, max_n, depth + 1)
R 1B
R 0B
L(i) 17
a[i][i] = ‘-’
L(k) 4
L(i) 17
V j = (i + pow(2, k)) % 17
a[i][j] = a[j][i] = ‘1’
L(row) a
print(row.join(‘ ’))
L(i) 17
idx[0] = i
I find_group(‘1’, i + 1, 17) | find_group(‘0’, i + 1, 17)
print(‘no good’)
L.break
L.was_no_break
print(‘all good’)</syntaxhighlight>
{{out}}
<pre>
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
all good
</pre>
=={{header|360 Assembly}}==
{{trans|C}}
<
RAMSEY CSECT
USING RAMSEY,R13 base register
Line 153 ⟶ 220:
XDEC DS CL12 temp xdeco
YREGS
END RAMSEY</
{{out}}
<pre>
Line 177 ⟶ 244:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f RAMSEYS_THEOREM.AWK
# converted from Ring
Line 203 ⟶ 270:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 224 ⟶ 291:
1101000100000000-1
</pre>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">global k, a, idx
k = 1
dim a(18,18)
dim idx(5)
for i = 0 to 17
a[i,i] = 2 #-1
next i
while k <= 8
for i = 1 to 17
j = (i + k) mod 17
if j <> 0 then
a[i,j] = 1 : a[j,i] = 1
end if
next i
k *= 2
end while
for i = 1 to 17
for j = 1 to 17
if a[i,j] = 2 then
print "- ";
else
print int(a[i,j]) & " ";
end if
next j
print
next i
# Es simétrico, por lo que solo necesita probar grupos que contengan el nodo 0.
for i = 0 to 17
idx[0] = i
if EncontrarGrupo(1, i+1, 17, 1) or EncontrarGrupo(0, i+1, 17, 1) then
print chr(10) & "No satisfecho."
exit for
end if
next i
print chr(10) & "Satisface el teorema de Ramsey."
end
function EncontrarGrupo(tipo, min, max, fondo)
if fondo = 0 then
c = ""
if tipo = 0 then c = "des"
print "Grupo totalmente "; c; "conectado:";
for i = 0 to 4
print " " & idx[i]
next i
print
return true
end if
for i = min to max
k = 0
for j = k to fondo
if a[idx[k],i] <> tipo then exit for
next j
if k = fondo then
idx[k] = i
if EncontrarGrupo(tipo, 1, max, fondo+1) then return true
end if
next i
return false
end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C}}==
Line 229 ⟶ 365:
No issue with the code or the output, there seems to be a bug with Rosettacode's tag handlers. - aamrun
<
int a[17][17], idx[4];
Line 290 ⟶ 426:
puts("all good");
return 0;
}</
{{out}} (17 x 17 connectivity matrix):
<pre>
Line 315 ⟶ 451:
=={{header|D}}==
{{trans|Tcl}}
<
/// Generate the connectivity matrix.
Line 371 ⟶ 507:
writefln("%-(%(%c %)\n%)", mat);
mat.ramseyCheck.writeln;
}</
{{out}}
<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 394 ⟶ 530:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def main(n\\17) do
vertices = Enum.to_list(0 .. n-1)
Line 449 ⟶ 585:
end
Ramsey.main</
{{out}}
Line 475 ⟶ 611:
=={{header|Erlang}}==
{{trans|C}} {{libheader|Erlang digraph}}
<
-export([main/0]).
Line 547 ⟶ 683:
++ [{wholly_connected,V1,V2,V3,V4}
|| {V1,V2,V3,V4,_,false} <- ListConditions]}
end.</
{{out}}
<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 572 ⟶ 708:
{{trans|Ring}}
{{trans|Go}}
<
Dim Shared As Integer i, j, k = 1
Dim Shared As Integer a(17,17), idx(4)
Line 635 ⟶ 771:
Print Chr(10) & "Satisface el teorema de Ramsey."
End
</syntaxhighlight>
{{out}}
<pre>
Line 661 ⟶ 797:
=={{header|Go}}==
{{trans|C}}
<
import "fmt"
Line 735 ⟶ 871:
}
fmt.Println("All good.")
}</
{{out}}
Line 760 ⟶ 896:
=={{header|J}}==
Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter: <
1 2 4 8
1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17 NB. Turn indices into bit mask
Line 805 ⟶ 941:
0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</
To test if all combinations of 4 rows and columns contain both a 0 and a 1
<syntaxhighlight lang="j">
comb=: 4 : 0 M. NB. All size x combinations of i.y
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
Line 820 ⟶ 956:
*./ (4 comb 17) checkRow ramsey 17
1
</syntaxhighlight>
=={{header|Java}}==
Translation of Tcl via D
{{works with|Java|8}}
<
import java.util.stream.IntStream;
Line 886 ⟶ 1,022:
System.out.println(ramseyCheck(mat));
}
}</
<pre>[-, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1]
Line 906 ⟶ 1,042:
[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, -]
Satisfies Ramsey condition.</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq.'''
With a minor tweak of the line using string interpolation, the following program also works with jaq (as of April 13, 2023), the Rust implementation of jq.
In the following, if a is a connectivity matrix and if $i != $j,
then a[$i][$j] is either 0 or 1 depending on whether the nodes are
unconnected or connected respectively.
<syntaxhighlight lang=jq>
# 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,
# 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.
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
| "Totally \($cs)connected group: " + (.idx | map(tostring) | join(" "))
else .i = $min
| until (.i >= $max or .emit;
.n = 0
| until (.n >= $depth or .a[.idx[.n]][.i] != $ctype;
.n += 1)
| if .n == $depth
then .idx[.n] = .i
| .emit = findGroup($ctype; 1; $depth+1)
else .
end
| .i += 1 )
| .emit // false
end ;
# Output: {a, idx}
def init:
def a:
[range(0;17) | 0] as $zero
| [range(0;17) | $zero]
| reduce range(0;17) as $i (.; .[$i][$i] = 2);
def idx: [range(0;4)|0];
{a: a, idx: idx, k: 1}
| until (.k > 8;
reduce range(0;17) as $i (.;
(($i + .k) % 17) as $j
| .a[$i][$j] = 1
| .a[$j][$i] = 1)
| .k *= 2 )
| del(.k);
# input: {a}
def printout:
def mark(n): "01-"[n:n+1];
.a as $a
| range(0; $a|length) as $i
| reduce range(0; $a|length) as $j (""; . + mark($a[$i][$j]) + " ") ;
# input: {a, idx}
def check:
first( range(0; .a|length) as $i
| .idx[0] = $i
| findGroup(1; $i+1; 1) // findGroup(0; $i+1; 1) // empty
| . + "\nNo good.")
// "All good." ;
init
| printout, check, "",
# Test case breakage
( .a[2][1] = 0
| .a[1][2] = 0
| printout, check )
</syntaxhighlight>
{{output}}
<pre>
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
All good.
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 0 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Totally unconnected group: 1 2 7 12
No good.
</pre>
=={{header|Julia}}==
{{trans|C}}
<
function findgroup(typ, nmin, nmax, depth)
Line 966 ⟶ 1,222:
testnodes()
</
<pre>
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 990 ⟶ 1,246:
=={{header|Kotlin}}==
{{trans|C}}
<
val a = Array(17) { IntArray(17) }
Line 1,042 ⟶ 1,298:
}
println("\nRamsey condition satisfied.")
}</
{{out}}
Line 1,067 ⟶ 1,323:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">g = CirculantGraph[17, {1, 2, 4, 8}]
vl = VertexList[g];
ss = Subsets[vl, {4}];
NoneTrue[ss, CompleteGraphQ[Subgraph[g, #]] &]
NoneTrue[ss, Length[ConnectedComponents[Subgraph[g, #]]] == 4 &]</syntaxhighlight>
{{out}}
[[File:Ramsey.png]]
<pre>True
True</pre>
=={{header|Mathprog}}==
{{lines too long|Mathprog}}
<syntaxhighlight lang="text">/*Ramsey 4 4 17
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully
Line 1,087 ⟶ 1,349:
clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5;
end;</
This may be run with:
<
The solution may be viewed on [[Solution Ramsey Mathprog|this page]].
In the solution file, the first section identifies the number of nodes connected in this clique. In the second part of the solution, the status of each arc in the graph (connected=<tt>1</tt>, unconnected=<tt>0</tt>) is shown.
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">var a: array[17, array[17, int]]
var idx: array[4, int]
proc findGroup(kind, minN, maxN, depth: int): bool =
if depth == 4:
echo "\nTotally ", if kind != 0: "" else: "un", "connected group:"
for i in 0..3:
stdout.write idx[i], if i == 3: '\n' else: ' '
return true
for i in minN..<maxN:
var n = depth
for m in 0..<depth:
if a[idx[m]][i] != kind:
n = m
break
if n == depth:
idx[n] = i
if findGroup(kind, 1, maxN, depth + 1):
return true
for i in 0..16: a[i][i] = 2
var j: int
var k = 1
while k <= 8:
for i in 0..16:
j = (i + k) mod 17
a[i][j] = 1
a[j][i] = 1
k = k shl 1
const Mark = "01-"
for i in 0..16:
for m in 0..16:
stdout.write Mark[a[i][m]], if m == 16: '\n' else: ' '
for i in 0..16:
idx[0] = i
if findGroup(1, i + 1, 17, 1) or findGroup(0, i + 1, 17, 1):
quit "\nRamsey condition not satisfied.", QuitFailure
echo "\nRamsey condition satisfied."</syntaxhighlight>
{{out}}
<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Ramsey condition satisfied.</pre>
=={{header|PARI/GP}}==
This takes the [[#C|C]] solution to its logical extreme.
<
check(M)={
Line 1,117 ⟶ 1,448:
M=matrix(17,17,x,y,my(t=abs(x-y)%17);t==2^min(valuation(t,2),3))
check(M)</
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use Math::Cartesian::Product;
Line 1,144 ⟶ 1,475:
print join(' ' ,@$_) . "\n" for @a;
print 'OK'</
{{out}}
<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 1,167 ⟶ 1,498:
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">),</span><span style="color: #000000;">17</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">findGroup</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">depth</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">depth</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">4</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">cs</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"un"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Totally %sconnected group:%s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">lo</span> <span style="color: #008080;">to</span> <span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">all_same</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">depth</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">all_same</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">all_same</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">idx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">depth</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">findGroup</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">depth</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">17</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">17</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'1'</span>
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'1'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- Test case breakage
--a[2][1]='0'; a[1][2]='0'</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">all_good</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">17</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">idx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">findGroup</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">findGroup</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">all_good</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">all_good</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"Satisfies Ramsey condition.\n"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"No good.\n"</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,251 ⟶ 1,586:
{{trans|C}}
<
a = [['0'] * 17 for i in range17]
idx = [0] * 4
Line 1,299 ⟶ 1,634:
exit()
print("all good")</
{{out|Output same as C}}
Line 1,310 ⟶ 1,645:
Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix).
<
(define N 17)
Line 1,323 ⟶ 1,658:
(λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))
(for ([row v]) (displayln row))</
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2018.08}}
<syntaxhighlight lang="raku"
my @a = [ 0 xx $n ] xx $n;
@a[$_;$_] = '-' for ^$n;
Line 1,342 ⟶ 1,677:
die "Bogus!" unless 0 < $links < 6;
}
say "OK";</
{{out}}
<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 1,365 ⟶ 1,700:
=={{header|REXX}}==
Mainline programming was borrowed from '''C'''.
<
/*
@.=0; #=17 /*initialize the node graph to zero. */
do d=0 for #; @.d.d= 2
end /*d*/
do k=1 by 0 while k<=8 /*K is doubled each time through loop.*/
do i=0 for #;
@.i.j= 1;
end /*i*/
k= k + k
end /*k*/
/* [↓] display a connection grid. */
do r=0 for #; _=; do c=0 for # /*build rows; build column by column. */
_= _ @.r.c
end /*c*/
say left('', 9) translate(_, "
end /*r*/
!.=
do v=0 for
do h=0 for # /*check column connections to the rows.*/
if @.v.h==1 then !._v.v= !._v.v + 1 /*if connected, then bump the counter.*/
end /*h*/ /* [↑]
ok= ok & !._v.v==# % 2
end /*v*/ /* divide the total by two.
/* [↓] check col. with row connections*/
do h=0 for # /*check the
do v=0 for # /*check the row connection to a column.*/
if @.h.v==1 then !._h.h= !._h.h + 1 /*if connected, then bump the counter.*/
end /*v*/ /* [↑]
ok= ok & !._h.h==# % 2
end /*h*/ /* divide the total by two.
say /*stick a fork in it, we're all done. */
say space("Ramsey's condition is"
{{out|output|text= ('''17x17''' connectivity matrix):}}
<pre>
1
1 1
0 1 1
1 0 1 1
0 1 0 1 1
0 0 1 0 1 1
0 0 0 1 0 1 1
1 0 0 0 1 0 1 1
1 1 0 0 0 1 0 1 1
0 1 1 0 0 0 1 0 1 1
0 0 1 1 0 0 0 1 0 1 1
0 0 0 1 1 0 0 0 1 0 1 1
1 0 0 0 1 1 0 0 0 1 0 1 1
0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Ramsey's condition is satisfied.
Line 1,425 ⟶ 1,760:
=={{header|Ring}}==
<
# Project : Ramsey's theorem
Line 1,451 ⟶ 1,786:
see nl
next
</syntaxhighlight>
Output:
<pre>
Line 1,474 ⟶ 1,809:
=={{header|Ruby}}==
<
17.times{|i| a[i][i] = '-'}
4.times do |k|
Line 1,489 ⟶ 1,824:
end
puts "Ok"
</syntaxhighlight>
{{out}}
<pre>
Line 1,514 ⟶ 1,849:
=={{header|Run BASIC}}==
{{incorrect|Run BASIC|The task has been changed to also require demonstrating that the graph is a solution.}}
<
for i = 1 to 17: a(i,i) = -1: next i
k = 1
Line 1,530 ⟶ 1,865:
next j
print
next i</
<pre>-1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
Line 1,551 ⟶ 1,886:
=={{header|Sidef}}==
{{trans|Ruby}}
<
17.times {|i| a[i][i] = '-' }
Line 1,567 ⟶ 1,902:
((0 < links) && (links < 6)) || die "Bogus!"
})
say "Ok"</
{{out}}
<pre>
Line 1,592 ⟶ 1,927:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
# Generate the connectivity matrix
Line 1,636 ⟶ 1,971:
puts [join $matrix \n]
ramseyCheck4 $matrix</
{{out}}
<pre>
Line 1,658 ⟶ 1,993:
Satisfies Ramsey condition
</pre>
=={{header|Wren}}==
{{trans|C}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
var a = List.filled(17, null)
for (i in 0..16) a[i] = List.filled(17, 0)
var idx = List.filled(4, 0)
var findGroup // recursive
findGroup = Fn.new { |ctype, min, max, depth|
if (depth == 4) {
var cs = (ctype == 0) ? "un" : ""
System.write("Totally %(cs)connected group:")
for (i in 0..3) System.write(" %(idx[i])")
System.print()
return true
}
var i = min
while (i < max) {
var n = 0
while (n < depth) {
if (a[idx[n]][i] != ctype) break
n = n + 1
}
if (n == depth) {
idx[n] = i
if (findGroup.call(ctype, 1, max, depth+1)) return true
}
i = i + 1
}
return false
}
var mark = "01-"
for (i in 0..16) a[i][i] = 2
var k = 1
while (k <= 8) {
for (i in 0..16) {
var j = (i + k) % 17
a[i][j] = 1
a[j][i] = 1
}
k = k << 1
}
for (i in 0..16) {
for (j in 0..16) Fmt.write("$s ", mark[a[i][j]])
System.print()
}
// Test case breakage
// a[2][1] = a[1][2] = 0
// It's symmetric, so only need to test groups containing node 0.
for (i in 0..16) {
idx[0] = i
if (findGroup.call(1, i+1, 17, 1) || findGroup.call(0, i+1, 17, 1)) {
System.print("No good.")
return
}
}
System.print("All good.")</syntaxhighlight>
{{out}}
<pre>
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
All good.
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// Rosetta Code problem: https://www.rosettacode.org/wiki/Ramsey%27s_theorem
// by Jjuanhdez, 06/2022
clear screen
k = 1
dim a(17,17), idx(4)
for i = 0 to 17
a(i,i) = 2 //-1
next i
sub EncontrarGrupo(tipo, mini, maxi, fondo)
if fondo = 0 then
c$ = ""
if tipo = 0 then c$ = "des" : fi
print "Grupo totalmente ", c, "conectado:"
for i = 0 to 4
print " ", idx(i)
next i
print
return true
end if
for i = mini to maxi
k = 0
for j = k to fondo
if a(idx(k),i) <> tipo then break : fi
next j
if k = fondo then
idx(k) = i
if EncontrarGrupo(tipo, 1, maxi, fondo+1) then return true : fi
end if
next i
return false
end sub
while k <= 8
for i = 1 to 17
j = mod((i + k), 17)
if j <> 0 then
a(i,j) = 1 : a(j,i) = 1
end if
next i
k = k * 2
wend
for i = 1 to 17
for j = 1 to 17
if a(i,j) = 2 then
print "- ";
else
print a(i,j), " ";
end if
next j
print
next i
// Es simétrico, por lo que solo necesita probar grupos que contengan el nodo 0.
for i = 0 to 17
idx(0) = i
if EncontrarGrupo(1, i+1, 17, 1) or EncontrarGrupo(0, i+1, 17, 1) then
print color("red") "\nNo satisfecho.\n"
break
end if
next i
print color("gre") "\nSatisface el teorema de Ramsey.\n"
end</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
|