Langford pairs are sequences if numbers where each number less than n occurs twice, and each occurrence of a value (i) is separated by i other numbers. For example for n=3:<\/p>\n
3 1 2 1 3 2<\/code><\/center><\/p>\nSo there you go. It’s a largely theoretical problem, though I think such sequences could have practical applications. For example, say you have a black box, caesar cypher encoder. You can feed it strings and look at the output in order to determine the substitution matrix being used… However the encoder embeds the message with a random amount of padding, and randomly discards parts of you message… Feeding the encoder a Langford pair may be an efficient way to determine the substitution matrix. Once encoded you can simply see which pairs are a given distance apart, the distance gives you the symbol number…<\/p>\n
Anyway.<\/p>\n
This is a silly hill climber for finding Langford pairs. There are surely better algorithms for doing this, and hill climbers don’t work particularly well! (solutions were at best 1 off for langford pairs beyond n=3. But I wonder what it is about the landscape that makes hill climbers perform badly here. As it’s almost a toy problem it might be interesting to play with a little.<\/p>\n
\nimport random\n\nsize = 7\n\ndef langfordscore(l):\n \n score = 0\n\n for i in range(1,size):\n idx = []\n for j in range(len(l)):\n if(l[j] == i):\n idx.append(j)\n\n if (abs(idx[0]-idx[1]) != (i+1)):\n score = score+1\n\n return score\n\ndef swap(l):\n i = random.randint(0,len(l)-1)\n j = random.randint(0,len(l)-1)\n\n nl = list(l)\n nl[i] = l[j]\n nl[j] = l[i]\n\n return nl\n\nlangford = []\n\nfor i in range(1,size):\n langford.append(i)\n langford.append(i)\n\nprint langford\n\nscore = 1000\nittr = 0\nlastmove = 0\nmutrate = 0\nwhile ((score != 0) and (ittr < 200000)):\n\n nlangford = swap(langford)\n\n for i in range(mutrate):\n nlangford = swap(nlangford)\n\n if (lastmove > 500):\n lastmove = 0\n mutrate = mutrate + 1\n \n if (mutrate > 5):\n mutrate = 0\n\n\n nscore = langfordscore(nlangford)\n \n if(nscore < score):\n langford = nlangford\n score = nscore\n print score\n print langford\n else:\n lastmove = lastmove + 1\n\n ittr = ittr + 1\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Langford pairs are sequences if numbers where each number less than n occurs twice, and each occurrence of a value (i) is separated by i other numbers. For example for n=3: 3 1 2 1 3 2 So there you go. It’s a largely theoretical problem, though I think such sequences could have practical applications. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-781","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-cB","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/781","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=781"}],"version-history":[{"count":2,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/781\/revisions"}],"predecessor-version":[{"id":783,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/781\/revisions\/783"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=781"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}