Ramsey's theorem: Difference between revisions

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|360 Assembly}}==

{{trans|C}}

RAMSEY CSECT

USING RAMSEY,R13 base register

XDEC DS CL12 temp xdeco

YREGS

{{out}}

<pre>

</pre>

 

 

=={{header|C}}==

For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization).

 

int a[17][17], idx[4];

puts("all good");

return 0;

{{out}} (17 x 17 connectivity matrix):

<pre>

=={{header|D}}==

{{trans|Tcl}}

 

/// Generate the connectivity matrix.

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

=={{header|Elixir}}==

{{trans|Erlang}}

def main(n\\17) do

vertices = Enum.to_list(0 .. n-1)

end

 

 

{{out}}

=={{header|Erlang}}==

{{trans|C}} {{libheader|Erlang digraph}}

-export([main/0]).

 

++ [{wholly_connected,V1,V2,V3,V4}

|| {V1,V2,V3,V4,_,false} <- ListConditions]}

{{out}}

<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1

 

Satisfies Ramsey condition.</pre>

 

=={{header|J}}==

1 2 4 8

1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17 NB. Turn indices into bit mask

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

 

To test if all combinations of 4 rows and columns contain both a 0 and a 1

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.

*./ (4 comb 17) checkRow ramsey 17

1

 

=={{header|Java}}==

Translation of Tcl via D

{{works with|Java|8}}

import java.util.stream.IntStream;

 

System.out.println(ramseyCheck(mat));

}

 

<pre>[-, 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, -]

Satisfies Ramsey condition.</pre>

 

=={{header|Kotlin}}==

{{trans|C}}

 

val a = Array(17) { IntArray(17) }

}

println("\nRamsey condition satisfied.")

 

{{out}}

</pre>

 

[[File:Ramsey.png]]

 

=={{header|Mathprog}}==

{{lines too long|Mathprog}}

This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully

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;

 

 

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|PARI/GP}}==

This takes the [[#C|C]] solution to its logical extreme.

 

check(M)={

 

M=matrix(17,17,x,y,my(t=abs(x-y)%17);t==2^min(valuation(t,2),3))

 

 

}

 

{{out}}

<pre>- 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 -

OK</pre>

 

=={{header|Python}}==

{{trans|C}}

 

a = [['0'] * 17 for i in range17]

idx = [0] * 4

exit()

 

 

{{out|Output same as C}}

 

=={{header|Racket}}==

{{incorrect|Racket|The task has been changed to also require demonstrating that the graph is a solution.}}

Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix).

 

(define N 17)

(λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))

 

 

=={{header|REXX}}==

Mainline programming was borrowed from &nbsp; '''C'''.

@.=0; #=17 /*initialize the node graph to zero. */

 

do k=1 by 0 while k<=8 /*K is doubled each time through loop.*/

/* [↓] display a connection grid. */

do r=0 for #; _=; do c=0 for # /*build rows; build column by column. */

end /*c*/

 

end /*r*/

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.*/

/* [↓] check col. with row connections*/

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.*/

say /*stick a fork in it, we're all done. */

{{out|output|text=&nbsp; ('''17x17''' connectivity matrix):}}

<pre>

 

Ramsey's condition is satisfied.

</pre>

 

=={{header|Ruby}}==

17.times{|i| a[i][i] = '-'}

4.times do |k|

end

a.each {|row| puts row.join(' ')}

(0...17).to_a.combination(4) do |quartet|

links = quartet.combination(2).map{|i,j| a[i][j].to_i}.reduce(:+)

end

puts "Ok"

{{out}}

<pre>

=={{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

next j

print

<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

=={{header|Sidef}}==

{{trans|Ruby}}

 

var j = ((i + 1<<k) % 17)

a[i][j] = (a[j][i] = 1)

a.each {|row| say row.join(' ') }

 

var links = quartet.combinations(2).map{|p| a.dig(p...) }.sum

((0 < links) && (links < 6)) || die "Bogus!"

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

# Generate the connectivity matrix

 

puts [join $matrix \n]

{{out}}

<pre>

Satisfies Ramsey condition

</pre>