Thue-Morse: Difference between revisions
(added haskell example) |
(→{{header|REXX}}: added the REXX language.) |
||
Line 122: | Line 122: | ||
01101001100101101001011001101001 |
01101001100101101001011001101001 |
||
0110100110010110100101100110100110010110011010010110100110010110</pre> |
0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
=={{header|REXX}}== |
|||
===using functions=== |
|||
<lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ |
|||
parse arg N . /*obtain the optional argument from CL.*/ |
|||
if N=='' | N=="," then N=80 /*Not specified? Then use the default.*/ |
|||
$= /*the Thue─Morse sequence (so far). */ |
|||
do j=0 to N /*generate sequence up to the Nth item.*/ |
|||
$=$ || $weight(j)//2 /*append the item to the Thue─Morse seq*/ |
|||
end /*j*/ |
|||
say $ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
$pop: return length(space(translate(arg(1),,0),0)) /*count 1's in number.*/ |
|||
$weight: return $pop(x2b(d2x(arg(1)))) /*dec──►bin, pop count*/</lang> |
|||
''output''' when using the default input: |
|||
<pre> |
|||
01101001100101101001011001101001100101100110100101101001100101101001011001101001 |
|||
</pre> |
|||
===using in-line code=== |
|||
<lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ |
|||
parse arg N . /*obtain the optional argument from CL.*/ |
|||
if N=='' | N=="," then N=80 /*Not specified? Then use the default.*/ |
|||
$= /*the Thue─Morse sequence (so far). */ |
|||
do j=0 to n /*generate sequence up to the Nth item.*/ |
|||
$=$ || length(space(translate(x2b(d2x(j)),,0),0))//2 /*append it to $.*/ |
|||
end /*j*/ |
|||
say $ /*stick a fork in it, we're all done. */</lang> |
|||
'''output''' is identical to the 1<sup>st</sup> REXX version. <br><br> |
|||
=={{header|SQL}}== |
=={{header|SQL}}== |
Revision as of 01:21, 5 October 2015
Make Thue-Morse sequence.
AWK
<lang AWK>BEGIN{print x="0"} {gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</lang>
C++
<lang cpp>
- include <iostream>
- include <iterator>
- include <vector>
int main( int argc, char* argv[] ) {
std::vector<bool> t; t.push_back( 0 ); size_t len = 1; std::cout << t[0] << "\n"; do { for( size_t x = 0; x < len; x++ ) t.push_back( t[x] ? 0 : 1 ); std::copy( t.begin(), t.end(), std::ostream_iterator<bool>( std::cout ) ); std::cout << "\n"; len = t.size(); } while( len < 60 ); return 0;
} </lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Haskell
<lang haskell>import Control.Monad
thueMorse = ap (++) (map (1-)) `iterate` [0]</lang>
Output: <lang haskell>~> thueMorse !! 5 [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]</lang>
J
We only show a prefix of the sequence:
<lang J> (, -.)@]^:[&0]9 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...</lang>
Java
<lang java>public class ThueMorse {
public static void main(String[] args) { sequence(6); }
public static void sequence(int steps) { StringBuilder sb1 = new StringBuilder("0"); StringBuilder sb2 = new StringBuilder("1"); for (int i = 0; i < steps; i++) { String tmp = sb1.toString(); sb1.append(sb2); sb2.append(tmp); } System.out.println(sb1); }
}</lang>
0110100110010110100101100110100110010110011010010110100110010110
OASYS Assembler
<lang oasys_oaa>; Thue-Morse sequence
[*'A] ; Ensure the vocabulary is not empty [&] ; Declare the initialization procedure %#1> ; Initialize length counter %@*> ; Create first object ,#1> ; Initialize loop counter
- ; Begin loop
%@<.#<PI ; Print current cell *.#%@<.#<NOT> ; Create new cell %@%@<NXT> ; Advance to next cell ,#,#<DN> ; Decrement loop counter ,#</ ; Check if loop counter is now zero %#%#<2MUL> ; Double length counter ,#%#<> ; Reset loop counter %@FO> ; Reset object pointer CR ; Line break
| ; Repeat loop</lang> The standard DOS-based interpreter will display an error message about word too long after 7 lines are output; this is because the 8th line does not fit in 80 columns.
Perl 6
<lang perl6>my @tm := 0, -> *@s { @s.map({ + not $_ }) } ... *;
say @tm[^64].join;</lang>
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Racket
<lang racket>#lang racket (define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0])) (define (thue-morse-step (s "0"))
(string-append s (list->string (map 1<->0 (string->list s)))))
(define (thue-morse n)
(let inr ((n (max (sub1 n) 0)) (rv (list "0"))) (if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))
(for-each displayln (thue-morse 7))</lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
REXX
using functions
<lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ parse arg N . /*obtain the optional argument from CL.*/ if N== | N=="," then N=80 /*Not specified? Then use the default.*/ $= /*the Thue─Morse sequence (so far). */
do j=0 to N /*generate sequence up to the Nth item.*/ $=$ || $weight(j)//2 /*append the item to the Thue─Morse seq*/ end /*j*/
say $ exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ $pop: return length(space(translate(arg(1),,0),0)) /*count 1's in number.*/ $weight: return $pop(x2b(d2x(arg(1)))) /*dec──►bin, pop count*/</lang> output' when using the default input:
01101001100101101001011001101001100101100110100101101001100101101001011001101001
using in-line code
<lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ parse arg N . /*obtain the optional argument from CL.*/ if N== | N=="," then N=80 /*Not specified? Then use the default.*/ $= /*the Thue─Morse sequence (so far). */
do j=0 to n /*generate sequence up to the Nth item.*/ $=$ || length(space(translate(x2b(d2x(j)),,0),0))//2 /*append it to $.*/ end /*j*/
say $ /*stick a fork in it, we're all done. */</lang>
output is identical to the 1st REXX version.
SQL
This example is using SQLite. <lang SQL>with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;</lang> You can add a LIMIT clause to the end to limit how many lines of output you want.
zkl
<lang zkl>fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }</lang> "12233334444" - "23"-->"14444" <lang zkl>str:="0"; do(7){ str=nextTM(str.println()) }</lang> println() returns the result it prints (as a string).
<lang zkl>fcn nextTM2{
var sb1=Data(Void,"0"), sb2=Data(Void,"1"); r:=sb1.text; sb1.append(sb2); sb2.append(r); r
}</lang> <lang zkl>do(7){ nextTM2().println() }</lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110