How to generate a binary string so to minimize weighted bitwise distance?

Question

I've got an array of weights, for example

[1, 0, 3, 5]

The distance between two strings is defined as a sum of weights for different bits, like this:

size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
  size_t result = 0;
  for (size_t i = 0; i < str1.size(); ++i) {
    if (str1[i] != str2.at(i))
      result += weights.at(i);
  }
  return result;
}

and starting string for example

'1101'

I need to generate strings in the way that strings with lowest distance from the original one go first, like this:

'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

I don't need code, I need just an algorithm which gets string of length N, array of weights of the same length and i as input and generates i-th combination, without generating the whole list and sorting it.

Answer 1

It is not possible to uniquely determine $i$-th combination because a function $f: \{0,1\}^* \to \mathbb{R}$ assigning distance to a string is not generally injective., that is - there may be multiple strings that correspond to a specific distance $d \in \mathbb{R}$ (which you example actually presents).

Also, it is not possible to know in advance all the possible distances as to determine which strings could be in $i$-th position, without actually calculating all the distances. It would be like knowing the shortest route to some destination by examining just that route.

I would suggest a different approach (but it will not make you happy as I generally think there is no way to achieve this in its fullest without generating all combinations); creating an algorithm that takes as input not $i$, but the distance $d$ and returns strings that are $d$ distance from your base string (note that it is in fact irrelevant). You can then eliminate from further process the weights that are larger than $d$ (and even ones equal to $d$, with further care).

• If you want all strings $d$ distance away and remaining weights vector is not too long, you can generate all subsets (a power set) of weights array and checking which has the sum $d$, but considering your restrictions on the solution - you do not want that because it would generate all the binary strings in the process.

• If you need just one string on distance $d$, no matter which, you can implement some backtracking search/sum on the weights array to find a combination that sums to $d$. (You can then store ones you got and repeat this process ignoring ones you found already, if you still want all.)

• You can model your problem as finding a path of length $d$ in a fully connected directed graph where you graph has $N$ nodes and the weight of an edge going to node $i$ is $weights[i]$. Then you can maybe use some optimized graph path finding (heuristic) algorithms, but that seems like an overkill.

I am quite sure this problem is in NP.