Challenge description
A Langford string of order N
is defined as follows:
- The length of the string is equal to
2*N
, - The string contains first
N
letters of the English alphabet, each letter appearing twice, - For each pair of the same letters, there are
M
letters between them, whereM
is that letter's position in the alphabet (A = 1
,B = 2
,...
,Z = 26
).
For instance, the only two possible Langford strings of order 3
are BCABAC
and CABACB
. As you can see, in both of these strings there is one letter between two A
's, two letters between B
's and three letters between C
's. Given a positive integer N
, output all Langford strings of order N
(in any reasonable format: print them one by one separated by a newline, return a list/array...).
Sample inputs / outputs
3: [CABACB, BCABAC]
4: [DACABDCB, BCDBACAD]
5: # no output #
7: [GCFBECBDGFEADA, GBFCBDECGFDAEA, GBDFBCEDGCFAEA, GCAFACDEGBFDBE, GADAFCEDGCBFEB, GACAFDCEGBDFBE, GDAEAFDCGEBCFB, GBDEBFCDGECAFA, EGBFCBEDCGFADA, CGDFCBEDBGFAEA, EGDAFAEDCGBFCB, EGBCFBECDGAFAD, AGABFDBECGDFCE, EGADAFECDGBCFB, AGABEFBCDGECFD, BGDBCEFDCGAEAF, FBGDBCEFDCGAEA, BFGBAEADFCGEDC, CFGACADEFBGDBE, EAGAFBEDBCGFDC, BCGBFCEADAGFED, DAGAFDBECBGFCE, EBGCBFECDAGAFD, CEGDCFBEDBGAFA, CEGBCFBEDAGAFD, BDGBCFDECAGAFE, EFAGACEDFCBGDB, DFAGADEBFCBGEC, AFAGBDEBFCDGEC, DFAGADCEFBCGBE, ECFGBCEBDFAGAD, DEFGADAECFBGCB, CDFGCBDEBFAGAE, EBDGBFEDACAGFC, CDEGCFDAEABGFB, AEAGCDFECBDGBF, FAEAGCDFECBDGB, DFCEGDCBFEBAGA, BFCBGDCEFADAGE, ECFDGCEBDFBAGA, DAFAGDCEBFCBGE, BCFBGCDEAFADGE, AEAFGBDEBCFDGC, ADAFGCDEBCFBGE, AFACEGDCFBEDBG, BFCBEGCDFAEADG, EBFDBGECDFACAG, BEFBCGDECFADAG, EBDFBGEDCAFACG, AEAFCGDECBFDBG, AEADFGCEDBCFBG, ADAEFGDBCEBFCG]
12: # <216288 strings> #
Notes
- Langford strings of order
N
can only be produced whenN ≡ 0 (mod 4)
orN ≡ 3 (mod 4)
, - You can use both lower-case and upper-case letters,
- You may use subsequent numbers as well (
012...
or123...
instead ofABC...
) - Order of strings in which they should appear as output is unspecified,
- Output can be quite lengthy (for instance, there are over 5 trillion distinct Langford strings of order
20
), so your program doesn't actually need to output them all, but it has to work in theory (given enough time and memory). - This challenge has been taken from /r/dailyprogrammer, all credit goes to /u/XenophonOfAthens