1
$\begingroup$

I was studying an algorithm on $k$-combinations of $n$-bit strings and realised that, my brute-force approach would spend lots of time on "structurally equivalent" bitstring combinations, that could be transformed into another bitstring combination for which a solution had already been computed by permuting bit-positions.

For readability I'll denote $n$-bit strings as elements of $2^{\{0,\dots,n-1\}}$, e.g. 1011 $= \{0,1,3\}$

Then, for $n=3$ and $k=2$, the only "unique" combinations are the following: $$ \{\emptyset, \{0\}\}\\ \{\emptyset, \{0, 1\}\}\\ \{\emptyset, \{0, 1, 2\}\}\\ \{\{0\}, \{1\}\}\\ \{\{0\}, \{0, 1\}\}\\ \{\{0\}, \{1, 2\}\}\\ \{\{0\}, \{0, 1, 2\}\}\\ \{\{0, 1\}, \{0, 2\}\}\\ \{\{0, 1\}, \{0, 1, 2\}\}\\ $$ $\{\{0\}, \{0, 2\}\}$ is not "unique", as it can be mapped to $\{\{0\}, \{0, 1\}\}$ by permuting $1$ and $2$.

Since it seems to me that others should have had similar problems before:

Is there a name for this subset of combinations?

P.S.: My best guess at a formal definition would be a set $X$, such that forall $A \in {2^n}^k$ ($k$-combinations of the powerset of $\{0,\dots,n-1\}$) $$ A \in X \Leftrightarrow A = \min\limits_\sigma(\sigma(A)) $$ i.e., $A$ is in $X$, iff it is the minimal element in the set of all pictures over all permutations (lifting permutations to sets of sets and taking the minimum over the lexicographical ordering).

$\endgroup$
  • $\begingroup$ You should also include the empty set in your possibilities as it represents the string with all bits $0$. Another possibility would then be $\{\emptyset,\{0\}\}$ and you can pair it with sets with $2$ or $3$ members. $\endgroup$ – Ross Millikan Oct 1 '18 at 16:52
  • $\begingroup$ Thanks, you are right. In the specific application I was interested in I was only concerned with bitstrings with at least one bit set, so I forgot to include those. I have updated the question accordingly. $\endgroup$ – jk. Oct 2 '18 at 7:27
0
$\begingroup$

You can characterize your pairs by giving the following:

  1. Number of elements in the first set, $f$
  2. Number of elements in the second set, $s$
  3. Number of elements in the intersection of the two sets, $t$

coupled with the requirement that the first set have no more elements than the second. Because you run out of distinct elements you must have $t \ge f+s-n$. The first set consists of the lowest $f$ numbers, $0$ through $f-1$. The second set consists of the lowest $t$ numbers and then the numbers from $f$ through $f+s-1-t$. If $k$ gets larger you can extend the number of elements list easily but the number of overlaps grows as $2^k-k-1$. I don't know of a name for it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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