Optimizing iteration over all permutations of a bit array

Question

edited for clarity:

I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ which satisfy the condition $T(x) = true$. I also know that if $b$ is a binary subset of $a$ then $f(a) > f(b)$ (e.g. $f(0b1101) > f(0b1001)$. I have no such insight about $T$. Can I avoid iterating over candidates which are subsets of inputs which satisfy $T$?

My current solution is this: beginning with $x = 1^n$ and an empty array as a cache, iterate through the various permutations in order of descending population count. Test if the next input $x$ is a subset of any values in the cache. If it is not a subset and $T(x)=true,ドル then compute $f(x)$ and add $x$ to the cache of supersets.

However, this strategy must search through the cache on every iteration. Instead, I am imagining a tree which (for $n=5$) looks like $0ドルb11111$$ $0ドルb11110\qquad0b11101\qquad0b11011\qquad0b10111\qquad0b01111$$ $$...$$ The root node is 1ドル^n,ドル and child nodes are created by changing a single 1ドル$ to a 0ドル$ so that all children are binary subsets of their parents. Iterating from the root node, when we reach a node $x$ for which $T$ is true, we could skip calculating $f$ or $T$ for all of its child nodes because they are binary subsets of $x$. Unfortunately, the tree as constructed has $n!$ nodes instead of 2ドル^n,ドル and nodes begin to appear multiple times in each sub-tree, so pruning the tree is not so simple. Is there a way to realize this type of optimization?

• Yuval Filmus: The maximum is $f(1^n)$. I suggest you rephrase your question to eliminate the function $f$. Explain what you want to accomplish only using the function $T$.
• Dylan MacKenzie: The maximum is not $f(1)$ and I believe both functions are required to understand the problem. $T(x)$ must be true for $f(x)$ to be valid and $T$ and $f$ are not related in any way. Perhaps I can help with some more specifics? It does feel a little wordy.
• Yuval Filmus: Bottomline – I cannot understand the problem you're trying to solve. Are you trying to maximize $f(x)$ over inputs such that $T(x)$? Moreover, you are assuming that $f$ is monotone. Do you have any assumptions on $T$?
• Dylan MacKenzie: Correct, I am trying to maximize $f(x)$ over inputs for which $T(x)$ is true, and there are no assumptions for $T$.
• Dylan MacKenzie: I edited the question to clarify my intent. Thank you. Also, I don't believe $f$ is strictly monotonic. $f(0b1000)$ is not necessarily greater than $f(0b0001)$ because 0ドルb0001$ is not a binary subset of 0ドルb1000$.

Answer 1

There's no possibility of an efficient algorithm here, unless you have more information about $T$. $T$ might only return true for one input and, in the worst case, you'd have to try all 2ドル^n$ possibilities for that input before finding the right one. Or $T$ could return true iff its input contains $n/2$ 1ドル$'s: there are exponentially many such strings and you'd have to try all of them to maximize $f,ドル since none of those strings is a binary subset of any of the others, so you have no information about the behaviour of $f$ on that set of strings.

• Dylan MacKenzie: I realized that this would do nothing for the worst case performance, but I was hoping there were some easy gains to be had for random input. I have yet to benchmark the "cache" idea; it might actually slow things down.