1: // Author & Copyright : Peter Luschny
2: // Created: 2011-12-01
3: // License: LGPL version 2.1 or (at your option)
4: // Creative Commons Attribution-ShareAlike 3.0
5:
6: using System;
7: using System.Collections;
8:
9: namespace BinaryCurves
10: {
11: class MeandersTest
12: {
13: static int CountMeanders(int m, int len)
14: {
15: var M = new Meanders(m, len);
16: return M.MeanderCount();
17: }
18:
19: static void PrintMeanders(int m, int len)
20: {
21: bool[] list = new bool[len];
22: var M = new Meanders(m, len);
23:
24: foreach (bool[] meander in M.MeanderList(list))
25: {
26: Meanders.PrintAsBinaryString(meander);
27: }
28: }
29:
30: static void Main()
31: {
32: string msg = "There are {0} meanders of length {1} with central angle {2}.";
33: int m = 2, len = 6, count;
34:
35: count = CountMeanders(m, len);
36: Console.WriteLine(msg, count, len, 360 / m);
37: PrintMeanders(m, len);
38: Console.ReadKey();
39: }
40: }
41:
42: public class Meanders
43: {
44: internal class Node
45: {
46: internal bool v; // value
47: internal bool s; // state
48: internal Node n; // next
49: internal Node(bool V, Node N)
50: {
51: v = V;
52: s = V;
53: n = N;
54: }
55: }
56:
57: Node head, tnode, inode;
58: Node[] node;
59: int m, len;
60: bool first;
61:
62: public Meanders(int m, int len)
63: {
64: if (len % m != 0)
65: {
66: throw new System.ArgumentException(
67: "len is not a multiple of m!");
68: }
69:
70: this.m = m;
71: this.len = len;
72: node = new Node[len];
73: }
74:
75: private void InitNodes(bool[] list)
76: {
77: first = true;
78: head = null; tnode = null; inode = null;
79:
80: int k = 0;
81: foreach (var val in list)
82: {
83: tnode = new Node(val, head);
84: node[k] = tnode;
85: head = tnode;
86:
87: if (head.n != null && AgtB(head.n.v, head.v))
88: {
89: throw new System.ArgumentException(
90: "Items are not sorted!");
91: }
92:
93: if (++k == 2)
94: {
95: inode = head;
96: }
97: }
98: }
99:
100: private IEnumerable Parts(bool[] q)
101: {
102: int a = m, i;
103:
104: while (true)
105: {
106: if (a > len) break;
107: for (i = 0; i < a; i++) q[i] = false;
108: for (i = a; i < len; i++) q[i] = true;
109: a = a + m;
110: yield return q;
111: }
112: }
113:
114: public IEnumerable MeanderList(bool[] candidat)
115: {
116: if (candidat.Length == 1)
117: {
118: candidat[0] = false;
119: yield return candidat;
120: }
121: else
122: {
123: var P = Parts(candidat);
124:
125: foreach (bool[] candidate in P)
126: {
127: InitNodes(candidate);
128:
129: while (HasNext())
130: {
131: GetNext(candidate);
132: if (IsMeander(m, candidate))
133: {
134: yield return candidate;
135: }
136: }
137: }
138: }
139: }
140:
141: public int MeanderCount()
142: {
143: if (len == 1 || m == len)
144: {
145: return 1;
146: }
147: else
148: {
149: if (m == 1)
150: {
151: return 1 << (len - 1);
152: }
153:
154: bool[] candidat = new bool[len];
155: var P = Parts(candidat);
156: int count = 0;
157:
158: foreach (bool[] candidate in P)
159: {
160: InitNodes(candidate);
161:
162: while (HasNext())
163: {
164: GetNext(candidate);
165: if (IsMeander(m, candidate))
166: {
167: count++;
168: }
169: }
170: }
171: return count;
172: }
173: }
174:
175: static public void PrintAsBinaryString(bool[] M)
176: {
177: string s = "";
178: foreach (var m in M)
179: {
180: s += m ? 'R' : 'L';
181: }
182: Console.WriteLine(s);
183: }
184:
185: private bool AgtB(bool A, bool B)
186: {
187: return A && !B;
188: }
189:
190: private bool AgeB(bool A, bool B)
191: {
192: return (A && !B) || (A && B) || (!A && !B);
193: }
194:
195: private void NewPerm(Node b)
196: {
197: var y = b;
198: int k = 0;
199:
200: while (y != null)
201: {
202: node[k++].s = y.v;
203: y = y.n;
204: }
205: }
206:
207: public bool IsMeander(int m, bool[] S)
208: {
209: var h = S[0];
210: if (h) return false;
211:
212: var vec = new int[m];
213: var max = S.Length / m;
214: var dir = 0;
215:
216: foreach (bool s in S)
217: {
218: if (s && h) dir++;
219: if (!s && !h) dir--;
220:
221: dir = (dir + m) % m;
222: var v = vec[dir] + 1;
223: vec[dir] = v;
224: if (v > max) return false;
225: h = s;
226: }
227: return true;
228: }
229:
230: private bool HasNext()
231: {
232: Node j, t, s;
233:
234: if (first)
235: {
236: NewPerm(head);
237: first = false;
238: return true;
239: }
240:
241: j = inode.n;
242: if (j.n == null && AgeB(j.v, head.v))
243: {
244: return false;
245: }
246:
247: s = j.n != null && AgeB(inode.v, j.n.v) ? j : inode;
248: t = s.n;
249: s.n = t.n;
250: t.n = head;
251:
252: if (AgtB(head.v, t.v)) { inode = t; }
253: j = inode.n;
254: head = t;
255: NewPerm(head);
256:
257: return true;
258: }
259:
260: private void GetNext(bool[] list)
261: {
262: int k = 0;
263: foreach (var p in node)
264: {
265: list[k++] = p.s;
266: }
267: }
268: }
269: }
270: