1
$\begingroup$

Suppose you're given a string $s$ that consists of lowercase alphabetic letters only. The length of the string is $n$. You are also given $n$ cards, which have lowercase alphabetic letters on the front and back. You want to arrange (shuffle and/or flip each card) the $n$ cards in an order that produces the string. You can use either side of a card, but obviously not both.

I am wondering if this problem can be converted to a Hungarian Algorithm problem? We essentially have a bipartite graph here. The left part consists of $n$ nodes representing each character in $s$. For each character in $s$, there is a subset of the $n$ cards that can can be used to create that character.

Can this be turned into a problem that can be solved with the Hungarian algorithm?

New contributor
roulette01 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
8
  • $\begingroup$ Have you tried carrying out your idea? Where did you get stuck? $\endgroup$ – Yuval Filmus Jul 22 at 6:32
  • $\begingroup$ I dont think this can be cast as a hungarian problem as there is no cost for each operation. Also the original problem I presume can be solved in about $O(n \log n)$ time via various sorting methods $\endgroup$ – Nikos M. Jul 22 at 8:20
  • $\begingroup$ @YuvalFilmus The only idea I have that I know works for certain is to form an adjacency list for each s[i] and then do DFS with backtracking. But that algorithm is $O(n! * n)$, I believe. I am trying to see if the Hungarian algorithm works because that would reduce the complexity down to polynomial time. $\endgroup$ – roulette01 Jul 22 at 11:42
  • $\begingroup$ @NikosM. Hm, I don't it's possible to solve this problem in sorting, let alone in O(n log n) time? You would sort the string s, I presume, but then, I don't think that makes the problem any easier? Each s[i] can still be formed with some subset of the given cards. $\endgroup$ – roulette01 Jul 22 at 11:44
  • $\begingroup$ I was thinking of sorting both the cards (as joint pairs front-back) and the string, and then try a match $\endgroup$ – Nikos M. Jul 22 at 15:24

Your Answer

roulette01 is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.