p.andrey
BAN USERlexicographic_permutation(arr):
n = length(arr)
len = n  1
p = {0, 1, 2, ..., n1}
while True:
k = len  1
while p[k] > p[k+1]:
k = 1
if k >= 0:
l = len
while p[k] > p[l]:
l = 1
p[k],p[l] = p[l],p[k]
reverse p[k + 1] up to p[n]
for i=0,n do
print(a[p[i]])
else:
break

p.andrey
January 16, 2019 This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.
connected(v, T)
visited[v] = True
flag = False
for u in adj(v) do
if (u == T) OR // this is the ending vertex, so True
(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
flag = True
if visited[u] == False then
flag = connected(u, T)
// no need to check further...
if flag == False then
break;
conn[v] = flag
return flag
MAIN:
flag = connected(S, T)
if flag == False then
NOT NECESSARILY CONNECTED
else
NECESSARILY CONNECTED

p.andrey
January 11, 2019 Basically, this is a combinatorics problem combined with dynamic programming.
So, compute the delta=sum(MAX)sum(MIN) for all k subsets that can be made and the smallest one is the solution.
Because the array/list is circular, the maximum number of elements that can be used in a subset with the last element from the list is nk, so I used another list b that generates all list that can be made.
Below is the bruteforce approach, but using dynamic programming the complexity can be improved considerably. That is, if a split has been already computed, then there is no need to do it again, instead, first time must be recorded in a table.
Anyway, the complexity of the bruteforce solution below is ~O(k*2^n).
Plus, if the table is implemented as a selfbalancing binary tree(i.e. redblack tree), then the lookup is improved to logarithmic.
subset(S, b, k, sol, min)
if size(S) == k then
if sum(S) <= n then
S[head] = s[head] + (nsum(S))
// we have a candidate solution here (k subsets from list b)
// if the candidate's delta is less than the current known one, then update
delta = do_delta(b, S) // delta does MAXMIN for split S
if delta < min then
min = candidate
sol = S
// now lets generate another solution
// first pop the head of the stack until it can be incremented thus
// to generate another candidate solution
POP(S)
while S[head] >= (nk+1) and head > 0 do
POP(S)
if head > 0 then
S[head] = S[head] + 1
subset (S, b, k, sol, min)
else if sum(S) < n then
PUSH(S, 1) // head = head +1 and S[head] = 1
subset (S, b, k, sol, min)
else
POP(S)
do_dMaxMin(b, k)
let min = infinity // minimum delta: sum(MAX)sum(MIN)
let sol = NIL // the solution (the split)
let S = NIL // a stack
call subset(S, b, k, sol, min)
return (sol, min)
MAIN:
input: let a be the list of numbers
input: let k be the number of subsets
let b be the current list of numbers
let sol to be the best split
let min to be the minimum delta
sol = NIL
min = infinity
b = a
for i=0 to nk do
if i>0 then
// this moves i elements from the beginning of a to the end of it (since a is circular)
b = concat(a[i+1:n], a[1:i])
// lets see the candidate solution
(candidate_sol, candidate_delta) = do_dMaxMin(b,k)
if (candidate_delta < min) then
sol = candidate_sol
min = candidate_delta
return (sol, min)

p.andrey
January 11, 2019 Open Chat in New Window
nlog(n) ?
 p.andrey January 16, 2019