Ramsey's theorem: Difference between revisions

{{trans|Python}}

V idx = [0] * 4

L.break

L.was_no_break

{{out}}

=={{header|360 Assembly}}==

{{trans|C}}

RAMSEY CSECT

USING RAMSEY,R13 base register

XDEC DS CL12 temp xdeco

YREGS

{{out}}

<pre>

=={{header|AWK}}==

# syntax: GAWK -f RAMSEYS_THEOREM.AWK

# converted from Ring

exit(0)

}

{{out}}

<pre>

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

k = 1

dim a(18,18)

next i

return false

{{out}}

<pre>Same as FreeBASIC entry.</pre>

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];

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

{{trans|Ring}}

{{trans|Go}}

Dim Shared As Integer i, j, k = 1

Dim Shared As Integer a(17,17), idx(4)

Print Chr(10) & "Satisface el teorema de Ramsey."

End

{{out}}

<pre>

=={{header|Go}}==

{{trans|C}}

import "fmt"

}

fmt.Println("All good.")

{{out}}

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

=={{header|Julia}}==

{{trans|C}}

function findgroup(typ, nmin, nmax, depth)

testnodes()

<pre>

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1

=={{header|Kotlin}}==

{{trans|C}}

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

}

println("\nRamsey condition satisfied.")

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

vl = VertexList[g];

ss = Subsets[vl, {4}];

NoneTrue[ss, CompleteGraphQ[Subgraph[g, #]] &]

{{out}}

[[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|Nim}}==

{{trans|Kotlin}}

var idx: array[4, int]

quit "\nRamsey condition not satisfied.", QuitFailure

{{out}}

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

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

use Math::Cartesian::Product;

print join(' ' ,@$_) . "\n" for @a;

{{out}}

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

=={{header|Phix}}==

{{trans|Go}}

<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: #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>

{{out}}

<pre>

{{trans|C}}

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

idx = [0] * 4

exit()

{{out|Output same as C}}

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|Raku}}==

(formerly Perl 6)

{{Works with|rakudo|2018.08}}

my @a = [ 0 xx $n ] xx $n;

@a[$_;$_] = '-' for ^$n;

die "Bogus!" unless 0 < $links < 6;

}

{{out}}

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

=={{header|REXX}}==

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

/*────────────────────────────────────────── totally connected nor totally unconnected. */

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

end /*h*/ /* divide the total by two. */

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

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

<pre>

=={{header|Ring}}==

# Project : Ramsey's theorem

see nl

next

Output:

<pre>

=={{header|Ruby}}==

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

4.times do |k|

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

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

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

{{trans|C}}

{{libheader|Wren-fmt}}

var a = List.filled(17, null)

}

}

{{out}}

=={{header|Yabasic}}==

// by Jjuanhdez, 06/2022

next i

print color("gre") "\nSatisface el teorema de Ramsey.\n"

{{out}}

<pre>Same as FreeBASIC entry.</pre>