13
$\begingroup$

There are 8 soldiers, gathering and lining up every morning for their military service. The commander at the head of these soldiers demands that the morning lineup of these soldiers be arranged differently for every next day according to the following rule:

  • Any three soldiers cannot be lined up next to each other in the same order for others days.

For example; If ABCDEFGH is the first arrangement for day 1, on the other days, ABC, BCD, CDE, DEF, EFG and FGH cannot be lined up next to each other in the same order any more, but ACB arrangement is okay for other days until used once since they are not in the same order.

What is the maximum number of days can this happen?

Improve this question
$\endgroup$
4
  • $\begingroup$ Was this intended to be solved by computers? Because two answers have taken a programming approach. If you don't want that then use the [no-computers] tag in the future. $\endgroup$
    – bobble
    Dec 26, 2020 at 17:17
  • 1
    $\begingroup$ @bobble both computer or no-computer is okay for me, that’s why i didnt add that tag since it may not be that easy even with computer in my opinion. $\endgroup$
    – Oray
    Dec 26, 2020 at 17:18
  • $\begingroup$ Is there more to this? I've tried playing with the generalized problem of $n$ (instead of 8) soldiers and $m$ (instead of 3) groups that can't repeat, and noticed that almost always we can find a solution that is equal to an upper bound (generalizing RobPratt's bound) except for some mysterious cases of $(n,m)$ like $(3,2),(5,2),(5,4),(7,6),...$ - assuming my implementation is correct. $\endgroup$
    – Vepir
    Dec 28, 2020 at 17:39
  • 1
    $\begingroup$ @Vepir I didnt get into much detail for this, but probably there is a generalization possibility exists since I found my answer with some other methodology. In my methodology, two letters for the beginning and ending do not repeat itself more than 2 times. This could give you a lead, I dont know :) $\endgroup$
    – Oray
    Dec 28, 2020 at 20:11

3 Answers 3

Reset to default
12
$\begingroup$

An easy upper bound is

$8\cdot 7\cdot 6 / 6 = 56$

because each day contributes $8-2=6$ triples out of $8\cdot 7 \cdot 6$. Here's an optimal solution with

56 days:

ABCEGFDH, ABEHDGCF, ADECBGHF, AEDCBHGF, AEGHCDFB, AGCBFDEH, BCDEFAHG, BDAEFGCH, BDHFECGA, BECFHGDA, BFGDEAHC, BHDCAFGE, CABGDFHE, CDBGFHAE, CEHFDAGB, CFEDGHAB, CFGHDBEA, CGDBAHEF, CGFADHEB, CHAGFEBD, CHEDBFAG, DAFBGECH, DAHFCGBE, DBHAFEGC, DFGBCAEH, DGFCHBAE, DHBFEACG, DHGAEBCF, EAFDBCHG, EBGAFCDH, EBHFGACD, EDFABHCG, EFHBGCDA, EGBACHDF, EHCFBDGA, EHGBDCFA, FAECDGBH, FBCGEHAD, FBHECAGD, FCBEGDHA, FCEAGHBD, FDCGHEAB, FHCBAGED, GADFEHBC, GAHDEBFC, GBFHDACE, GCAHBEFD, GDCEBAFH, GEADCHFB, GFBEDHCA, HACFDGEB, HCEFBADG, HEGABDFC, HFACBDEG, HGCEDABF, HGEFCADB

I used integer linear programming as follows. For each of the $8!=40320$ permutations $p \in P$, let binary decision variable $x_p$ indicate whether that permutation appears. For each of the $8\cdot 7\cdot 6=336$ triples $t\in T$, let $P_t \subset P$ be the subset of permutations that contain that triple. The problem is to maximize $$\sum_{p\in P} x_p \tag1$$ subject to $$\sum_{p\in P_t} x_p \le 1 \quad \text{for $t\in T$} \tag2.$$ The objective $(1)$ maximizes the number of days, and the constraint $(2)$ enforces that each triple appears at most once.

Improve this answer
$\endgroup$
8
  • $\begingroup$ good way to find, congratz! $\endgroup$
    – Oray
    Dec 26, 2020 at 18:06
  • $\begingroup$ If you don't mind answering, what did you use to solve this integer linear programming task and how long did it took? - I'm not familiar with linear programming, but was inspired by this to finally look into it. A google search lead me to a python modeler PuLP that can call GLPK. - But, the solving process is taking forever. I've tried setting an 1 hour time out, but the best solution it found under that time constrain was 54 days. Was this to be expected? I'd love to know what tools and tricks or references would you recommend to help improve the solving time, if you don't mind. $\endgroup$
    – Vepir
    Dec 28, 2020 at 2:24
  • 1
    $\begingroup$ This problem can be much harder to solve if your solver does not exploit symmetry because the branch-and-bound algorithm will then perform redundant work by processing essentially identical tree nodes. One workaround is to fix $x_p=1$ for one permutation, say ABCDEFGH, although this still does not eliminate all symmetry. The presolver will remove this fixed variable, any other variables that are then forced to $0$, and any constraints that then become redundant. $\endgroup$
    – RobPratt
    Dec 28, 2020 at 6:07
  • 1
    $\begingroup$ Another idea that might help to find 56 is to change the $\le 1$ to $=1$. $\endgroup$
    – RobPratt
    Dec 28, 2020 at 17:08
  • 1
    $\begingroup$ This is a set packing problem or “maximum independent set” problem or “node packing” problem in the graph defined in @Vepir’s answer. You could try any heuristics or exact approaches for those problems. For example, maybe try a local search that involves two moves: adding an unused node (as in the greedy heuristic) or replacing a used node with two unused nodes. $\endgroup$
    – RobPratt
    Nov 10, 2021 at 13:15
5
$\begingroup$

My answer:

39

My method:

I programed this python program that used brute force to find all the possible arrangements: 

from itertools import permutations

letters = "ABCDEFGH"
windows = len(letters) - 2
done = list()

for p in permutations(letters):
    for i in range(windows):
        if any("".join(p[i:i+3]) in array for array in done):
            break
    else:
        print("".join(p))
        done.append("".join(p))
print(len(done))

Explanation of my method:

The concept is really simple: the letters variable (of type str) stores all the possible positions per arrangement, the windows variable (of type int) stores the number of windows of 3 in a line there can be per 8 (len(letters)) positions, and the done variable (of type list) will store all the qualified positions.

I imported the permutations method from the built-in itertools module, that will allow me to make the program iterate through and access every permutation of the letters string.

With each permutation of letters, iterate through each window of three positions, and check to see if any strings in the done list contains the current window. If found, set break out of the loop.

Only append the current permutation of letters if unique remains no break statement was met during the inner iterations, and at the end, print the number of qualified permutations found with the built-in len() method.

Output of my method:

Here are all the valid arrangements of soldiers: 

ABCDEFGH
ABDCEFHG
ABECDGFH
ABFCDHEG
ABGCDFEH
ABHCEDFG
ACBDEGHF
ACDBEHFG
ACEBDHGF
ACFBDGEH
ACGBDFHE
ACHBEFDG
ADBCGHEF
ADCBHFEG
ADEBFGCH
ADFBCEHG
ADGBFECH
ADHBCFGE
AEBCHGDF
AECBFHDG
AEDBGFCH
AEFBGDCH
AEGBHDCF
AEHBFDCG
AFBEDGHC
AFCBEGDH
AFDBHECG
AFEDHCBG
AFHBGEDC
AHDFCGEB
BAFGDEHC
BAGECFDH
BAHCGFDE
BDAHFCEG
BFAGHDEC
BHGCFEAD
CDAGFEBH
CHEAGDBF
FGBCAHED
39

Improve this answer
$\endgroup$
0
3
$\begingroup$

Greedy strategy gives at most (not optimal but close)

54 days

where the greedy strategy was to

Every day, consider only available permutations that share their triplets with the largest number of unavailable permutations. That is, every day decrease the set of available permutations by the smallest amount possible.

In other words, in terms of graph theory:

I constructed a graph $G$ whose vertices are the permutations, $|V|=8!=40320$.

Two vertices $v,w\in V$ are connected by an edge if and only if they cannot form a solution together. Then, the degree of every vertex will be $d(v)=3623$.

Let $N(v)$ denote the set of neighbors of $v\in V$ and $\overline{N}(v)=N(v)\cup\{v\}$. If we include vertex $v\in V$ in our solution, then vertices in $\overline{N}(v)$ are unusable (cannot be included in our solution).

My greedy strategy was as follows:

  1. Let $X_n\subset V$ and WLOG start with any vertex $v\in V$, i.e. $X_1=\{v\}$.

  2. Let $Y=\bigcup\limits_{x\in X_n} \overline{N}(x)$ and $X_{n+1}=X_{n}\cup\{z\}$ s.t. $z\in V\setminus Y$ maximizes $|N(z)\cap Y|$.

That is, at every step we pick a new vertex $z$ such that the set of unusable vertices $Y$ grows by the smallest amount possible. If there are multiple choices, we can try all of them.

There are 16 scenarios that result in solutions of 54 days, while other scenarios result in less. That is, we cannot get more than 54 days using this greedy strategy.

solution 54 ['01234567', '05634127', '73405126', '71205346', '03476125', '05763124', '13427605', '26305471', '46371052', '16324705', '24063571', '27160354', '52460713', '71560243', '36015724', '26045731', '67145230', '61527304', '27031546', '07624153', '46721503', '24536701', '31425706', '25370461', '36170254', '53014627', '02746531', '06147532', '54261307', '25610473', '75214306', '03647251', '51407236', '40327516', '45103726', '35172064', '31065742', '42107365', '54102673', '74013526', '74165203', '65132074', '41362507', '73562041', '41732650', '07543162', '21376540', '17564023', '50623174', '23745016', '01764235', '67504321', '02164375', '16743502']
solution 54 ['01234567', '05634127', '73405126', '71205346', '03476125', '05763124', '13427605', '26305471', '46371052', '16324705', '24063571', '27160354', '52460713', '71560243', '36015724', '26045731', '67145230', '61527304', '27031546', '07624153', '46721503', '24536701', '31425706', '25370461', '36170254', '53014627', '02746531', '06147532', '54261307', '25610473', '75214306', '03647251', '51407236', '40327516', '45103726', '35172064', '31065742', '42107365', '54102673', '74013526', '74165203', '65132074', '41362507', '73562041', '41732650', '07543162', '21376540', '17564023', '50623174', '23745016', '01764235', '67504321', '16743502', '02164375']
solution 54 ['01234567', '05634127', '73405126', '71205346', '03476125', '05763124', '13427605', '26305471', '46371052', '16324705', '24063571', '27160354', '52460713', '71560243', '36015724', '26045731', '67145230', '61527304', '27031546', '07624153', '46721503', '24536701', '31425706', '25370461', '36170254', '53014627', '02746531', '06147532', '54261307', '25610473', '75214306', '03647251', '51407236', '40327516', '45103726', '35172064', '31065742', '42107365', '54102673', '74013526', '74165203', '65132074', '41362507', '04173265', '73564201', '75620431', '06754321', '21643750', '50162374', '74350621', '31674502', '02137645', '17650423', '65402317']
solution 54 ['01234567', '05634127', '73405126', '71205346', '03476125', '05763124', '13427605', '26305471', '46371052', '16324705', '24063571', '27160354', '52460713', '71560243', '36015724', '26045731', '67145230', '61527304', '27031546', '07624153', '46721503', '24536701', '31425706', '25370461', '36170254', '53014627', '02746531', '06147532', '54261307', '25610473', '75214306', '03647251', '51407236', '40327516', '45103726', '35172064', '31065742', '42107365', '54102673', '74013526', '74165203', '65132074', '41362507', '04173265', '73564201', '75620431', '06754321', '21643750', '50162374', '74350621', '31674502', '02137645', '17650423', '64023175']
solution 54 ['01234567', '05634127', '15627340', '13427560', '25610347', '35641027', '27105346', '60327415', '52760413', '27035416', '60241735', '32471605', '46071352', '43571260', '35026714', '64023715', '74523601', '37405261', '13264705', '42635107', '47265013', '67014235', '17025364', '61370425', '32570614', '05136742', '64213057', '54203617', '07461532', '40376125', '17436520', '62503147', '14507362', '16205473', '15047623', '31750624', '53021764', '21407653', '40157632', '15246730', '47521630', '30754621', '07251463', '63751240', '72154063', '51643207', '73210465', '45731206', '30645172', '16723045', '24531067', '65437201', '20431657', '57243016']
solution 54 ['01234567', '05634127', '15627340', '13427560', '25610347', '35641027', '27105346', '60327415', '52760413', '27035416', '60241735', '32471605', '46071352', '43571260', '35026714', '64023715', '74523601', '37405261', '13264705', '42635107', '47265013', '67014235', '17025364', '61370425', '32570614', '05136742', '64213057', '54203617', '07461532', '40376125', '17436520', '62503147', '14507362', '16205473', '15047623', '31750624', '53021764', '21407653', '40157632', '15246730', '47521630', '30754621', '07251463', '63751240', '72154063', '51643207', '73210465', '45731206', '30645172', '16723045', '24531067', '65437201', '57243016', '20431657']
solution 54 ['01234567', '05634127', '15627340', '13427560', '25610347', '35641027', '27105346', '60327415', '52760413', '27035416', '60241735', '32471605', '46071352', '43571260', '35026714', '64023715', '74523601', '37405261', '13264705', '42635107', '47265013', '67014235', '17025364', '61370425', '32570614', '05136742', '64213057', '54203617', '07461532', '40376125', '17436520', '62503147', '14507362', '16205473', '15047623', '31750624', '53021764', '21407653', '40157632', '15246730', '47521630', '30754621', '07251463', '21540637', '67531240', '64375120', '65432017', '72043165', '30451672', '65172430', '57230164', '23104657', '45372106', '06457321']
solution 54 ['01234567', '05634127', '15627340', '13427560', '25610347', '35641027', '27105346', '60327415', '52760413', '27035416', '60241735', '32471605', '46071352', '43571260', '35026714', '64023715', '74523601', '37405261', '13264705', '42635107', '47265013', '67014235', '17025364', '61370425', '32570614', '05136742', '64213057', '54203617', '07461532', '40376125', '17436520', '62503147', '14507362', '16205473', '15047623', '31750624', '53021764', '21407653', '40157632', '15246730', '47521630', '30754621', '07251463', '21540637', '67531240', '64375120', '65432017', '72043165', '30451672', '65172430', '57230164', '23104657', '45372106', '20645731']
solution 54 ['01234567', '05634127', '51267340', '53467120', '61250347', '31245067', '67501342', '20367451', '16720453', '67031452', '20645731', '36475201', '42075316', '43175620', '31062754', '24063751', '74163205', '37401625', '53624701', '46231507', '47621053', '27054631', '57061324', '25370461', '36170254', '01532746', '24653017', '14603257', '07425136', '40372561', '57432160', '26103547', '54107326', '52601473', '51047263', '35710264', '13065724', '65407213', '40517236', '51642730', '47165230', '30714265', '07615423', '65140237', '27135640', '24371560', '21436057', '76043521', '30415276', '21576430', '17630524', '63504217', '41376502', '60241735']
solution 54 ['01234567', '05634127', '51267340', '53467120', '61250347', '31245067', '67501342', '20367451', '16720453', '67031452', '20645731', '36475201', '42075316', '43175620', '31062754', '24063751', '74163205', '37401625', '53624701', '46231507', '47621053', '27054631', '57061324', '25370461', '36170254', '01532746', '24653017', '14603257', '07425136', '40372561', '57432160', '26103547', '54107326', '52601473', '51047263', '35710264', '13065724', '65407213', '40517236', '51642730', '47165230', '30714265', '07615423', '65140237', '27135640', '24371560', '21436057', '76043521', '30415276', '21576430', '17630524', '63504217', '41376502', '02417365']
solution 54 ['01234567', '05634127', '51267340', '53467120', '61250347', '31245067', '67501342', '20367451', '16720453', '67031452', '20645731', '36475201', '42075316', '43175620', '31062754', '24063751', '74163205', '37401625', '53624701', '46231507', '47621053', '27054631', '57061324', '25370461', '36170254', '01532746', '24653017', '14603257', '07425136', '40372561', '57432160', '26103547', '54107326', '52601473', '51047263', '35710264', '13065724', '65407213', '40517236', '51642730', '47165230', '30714265', '07615423', '23715640', '76514023', '15243607', '73650421', '41735602', '30241576', '52763041', '64135027', '21437605', '17643052', '60435217']
solution 54 ['01234567', '05634127', '51267340', '53467120', '61250347', '31245067', '67501342', '20367451', '16720453', '67031452', '20645731', '36475201', '42075316', '43175620', '31062754', '24063751', '74163205', '37401625', '53624701', '46231507', '47621053', '27054631', '57061324', '25370461', '36170254', '01532746', '24653017', '14603257', '07425136', '40372561', '57432160', '26103547', '54107326', '52601473', '51047263', '35710264', '13065724', '65407213', '40517236', '51642730', '47165230', '30714265', '07615423', '23715640', '76514023', '15243607', '73650421', '41735602', '30241576', '52763041', '64135027', '21437605', '60435217', '17643052']
solution 54 ['01234567', '05634127', '73401562', '75601342', '03472561', '01723564', '53467201', '62301475', '42375016', '52364701', '64023175', '67520314', '16420753', '75120643', '32051764', '62041735', '27541630', '25167304', '67035142', '07264513', '42765103', '64132705', '35461702', '61370425', '32570614', '13054267', '06742135', '02547136', '14625307', '61250473', '71654302', '03247615', '15407632', '40367152', '41503762', '31576024', '35021746', '46507321', '14506273', '74053162', '74521603', '21536074', '45326107', '73126045', '45736210', '07143526', '65372140', '57124063', '10263574', '63741052', '05724631', '27104365', '52743106', '06524371']
solution 54 ['01234567', '05634127', '73401562', '75601342', '03472561', '01723564', '53467201', '62301475', '42375016', '52364701', '64023175', '67520314', '16420753', '75120643', '32051764', '62041735', '27541630', '25167304', '67035142', '07264513', '42765103', '64132705', '35461702', '61370425', '32570614', '13054267', '06742135', '02547136', '14625307', '61250473', '71654302', '03247615', '15407632', '40367152', '41503762', '31576024', '35021746', '46507321', '14506273', '74053162', '74521603', '21536074', '45326107', '73126045', '45736210', '07143526', '65372140', '57124063', '10263574', '63741052', '05724631', '27104365', '06524371', '52743106']
solution 54 ['01234567', '05634127', '73401562', '75601342', '03472561', '01723564', '53467201', '62301475', '42375016', '52364701', '64023175', '67520314', '16420753', '75120643', '32051764', '62041735', '27541630', '25167304', '67035142', '07264513', '42765103', '64132705', '35461702', '61370425', '32570614', '13054267', '06742135', '02547136', '14625307', '61250473', '71654302', '03247615', '15407632', '40367152', '41503762', '31576024', '35021746', '46507321', '14506273', '74053162', '74521603', '21536074', '45326107', '04573621', '73124605', '71260435', '02714365', '65243710', '10526374', '74310265', '35274106', '06537241', '57210463', '21406357']
solution 54 ['01234567', '05634127', '73401562', '75601342', '03472561', '01723564', '53467201', '62301475', '42375016', '52364701', '64023175', '67520314', '16420753', '75120643', '32051764', '62041735', '27541630', '25167304', '67035142', '07264513', '42765103', '64132705', '35461702', '61370425', '32570614', '13054267', '06742135', '02547136', '14625307', '61250473', '71654302', '03247615', '15407632', '40367152', '41503762', '31576024', '35021746', '46507321', '14506273', '74053162', '74521603', '21536074', '45326107', '04573621', '73124605', '71260435', '02714365', '65243710', '10526374', '74310265', '35274106', '06537241', '57210463', '24063571']

(Assuming my python implementation is correct.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is it possible to tweak your method and arrive at the optimal answer ? $\endgroup$
    – Hemant Agarwal
    Nov 10, 2021 at 10:26
  • $\begingroup$ @HemantAgarwal You could continue with this greedy solution and apply something along the lines of a local search (tabu search, ...) to try to escape the local optimum, but landing into the global optimum is not always guaranteed when using heuristic programming. $\endgroup$
    – Vepir
    Nov 10, 2021 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.