3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think it is not possible to generate desired $i$-th combination without creating all combinations up to $i$-th. $\endgroup$ – Sandro Lovnički Aug 26 '18 at 19:17
  • $\begingroup$ 1. But generating the whole list and then sorting it is the obvious way to solve it. What's wrong with that solution? Is it space complexity that you are trying to minimize? 2. Are the weights small? Are you looking for an algorithm where the running time per output is polynomial in the largest weight; or in the length of the largest weight (in bits); or something else? $\endgroup$ – D.W. Aug 27 '18 at 4:53
  • 1
    $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/41449/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Aug 27 '18 at 4:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't agree with your first paragraph. If we require that the strings be sorted first by distance, with ties broken by lexicographic order, then the ordering is uniquely determined. $\endgroup$ – D.W. Aug 27 '18 at 4:54
  • $\begingroup$ The problem is not in NP: it is not a search problem, so it isn't in NP. $\endgroup$ – D.W. Aug 27 '18 at 4:55

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.