Optimizing iteration over all permutations of a bit array

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 $$0b11111$$ $$0b11110\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?

• 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$. – Yuval Filmus May 22 '15 at 5:59
• 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. – Dylan MacKenzie May 22 '15 at 6:04
• 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$? – Yuval Filmus May 22 '15 at 6:17
• 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 May 22 '15 at 6:19
• 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 $0b0001$ is not a binary subset of $0b1000$. – Dylan MacKenzie May 22 '15 at 6:29

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.