Struny Langford

11

Opis wyzwania

Langford ciąg zamówienia Njest zdefiniowana w następujący sposób:

  • Długość łańcucha jest równa 2*N,
  • Ciąg zawiera pierwsze Nlitery alfabetu angielskiego, każda litera pojawia się dwukrotnie,
  • Dla każdej pary tych samych liter, istnieje Mlistów między nimi, gdzie Mjest stanowisko, że pismo w alfabecie ( A = 1, B = 2, ..., Z = 26).

Na przykład jedyne dwa możliwe ciągi porządkowe Langford 3to BCABACi CABACB. Jak widać, w obu tych ciągach jest jedna litera między dwiema A, dwie litery między Bi trzy litery między C. Biorąc pod uwagę dodatnią liczbę całkowitą N, Nwypisz wszystkie ciągi znaków Langforda (w dowolnym rozsądnym formacie: wydrukuj je jeden po drugim oddzielone znakiem nowej linii, zwróć listę / tablicę ...).

Przykładowe wejścia / wyjścia

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

Notatki

  • Ciągi zamówień Langforda Nmogą być produkowane tylko wtedy , gdy N ≡ 0 (mod 4)lubN ≡ 3 (mod 4)
  • Możesz używać zarówno małych, jak i wielkich liter,
  • Możesz także użyć kolejnych numerów ( 012...lub 123...zamiast ABC...)
  • Kolejność ciągów, w których powinny pojawiać się jako dane wyjściowe, jest nieokreślona,
  • Dane wyjściowe mogą być dość długie (na przykład istnieje ponad 5 trylionów odrębnych ciągów kolejności Langforda 20), więc twój program nie musi tak naprawdę wyprowadzać ich wszystkich, ale musi działać teoretycznie (biorąc pod uwagę wystarczającą ilość czasu i pamięci).
  • To wyzwanie zostało wzięte z / r / dailyprogrammer , wszystkie podziękowania należą się / u / XenophonOfAthens
shooqie
źródło
4
W piaskownicy jest ściśle powiązane wyzwanie. Chociaż nie jest to w żaden sposób wymagane, zwykle jest dobrym pomysłem i prawdopodobnie grzeczne jest sprawdzenie tam również duplikatów.
Martin Ender
Czy możemy po prostu wypisać tablicę liczb?
Leaky Nun
@LeakyNun: Jasne, czemu nie. Zaktualizowałem opis.
shooqie,
1
Odnoszę się do tego (uruchom program)
Leaky Nun

Odpowiedzi:

3

CJam (23 bajty)

{,2*e!{__f{\a/1=,(}=},}

Demo online . Jest to anonimowy blok (funkcja), który pobiera dane wejściowe ze stosu i pozostawia dane wyjściowe na stosie w postaci tablicy tablic liczb całkowitych sekwencyjnych opartych na 0.

Peter Taylor
źródło