组合:将角色分组挑战

Question

我正在研究工作中的一些分组问题.有很多问题,请耐心等待.我发现它们非常有趣.如果这里的任何人对组合学也感兴趣,请帮助我.

好吧,我们有一堆人物,在这里我已经采取了援助措施.

1. 我们可以将这些元素分组的方式是什么？让我们说我们有4个字符的帮助.有效组(保留订单)将是:

   助剂
   的AI DS
   一的id
   的AI DS
   的AI DS
   一个IDS
   助剂小号
   助剂

你如何列举所有的团体？你能告诉我任何n个字母有多少组合？

2.特别案例

• 如果案件像Ai sd和ai sd这两个群体有所不同怎么办？

• 您需要花多少时间列举所有案例？找到4个字母和5个字母之间的时差是多少？

• 如果将"空格"作为字符.在所有枚举之后,你会写出多少个字符？

• 如果您根据距离定义从单词到另一个单词的变换.说"ai ds"和"ai ds"有1个距离,因为你应该将字母"i"移动一步.你能找到任何单词两边n个距离的单词吗？

编辑:
"艾滋病"是一个单词.
"ids""援助s"是与原始单词"aids"相距1个距离的两个单词.
"id s"是与原始单词"aids"相距两个距离的单词.
"援助s"是一个距离这个词三个距离的词.

这个问题似乎是金矿.

额外奖励:两个单词之间的最小距离是多少.就像"艾滋病"一样,距离"ids"还有两个距离.是否有一个"中点"单词,您可以在最小距离的枚举中找到任何其他单词？从一个单词到另一个单词有多少条路径？

Answer 1

计算组合的数量是微不足道的.基本上,每两个字母之间有一个字符.它可能是"epsilon"(空)或空格.因此,对于n个字母,您有n-1个这样的分隔符.由于每个字符只能有两个值,因此它与n-1个数字的二进制数相同.所以你可以拥有2到n-1组合的力量.

aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations

现在,针对特殊情况.如果每个字符可以是小写字母或大写字母,则字符的n个变量的幂为2(只要它们是字母).现在,上面的每个组合具有基于大写的 2 n个变化,因此最终结果是(2(n-1))*(2**n),其等于2**(2*n -1).

对于每个附加字母,您可以将列举它们所需的时间加倍或四倍(取决于大写字母),这可以从公式中轻松理解.

字符总数有点困难,但足以注意到每个"空格"是"epsilon"的一半.所以我们有(2**(n-1))*n(字母)+((2**(n-1))*(n-1))/ 2(空格).在示例中:

(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters

最后,距离问题与Levenshtein距离有关.我想过使用Burkhard-Keller树,但我现在看到这根本没有必要,因为问题相当简单.

首先,使一个字符串等于另一个字符串所需的最小插入/删除/更改次数称为Levenshtein距离.这直接适用于问题:添加空格,删除空格,根据需要更改小写/大写.通常,这最好通过动态编程来解决,动态编程通常可以被认为是将解决方案的数据保存到问题的一小部分,然后重复使用计算其他部分/更大的部分.

但考虑到我们问题的特殊限制,我们可以比较代表空格/ epsilon的"二进制"数字.

假设函数f(word)将返回表示该单词中空格的二进制数.例如,对于"ai ds",它将返回"010",对于"aid s",它将返回"111".每个组合之间的变化数量是通过对f(010 xor 111 = 101)的结果进行异或,然后计算等于1的位数来给出的.让我们在Scala中编写几个函数:

def spacesToBinary(s: String) = {
  (s zip s.drop(1)) // transform "ai ds" into ((a,i), (i, ), ( ,d), (d, s))
  .foldLeft(0) { (binary, pair) => pair match {
      case (' ', _) => binary            // A space is always followed by a letter,
                                         // so we ignore it
      case (_, ' ') => (binary << 1) | 1 // If a letter is followed by a space, bit = 1
      case _ => binary << 1              // If not, bit = 0
  }}
}

def numberOfOnes(d: Int) = {
  var bits = 0
  var n = d
  while(n != 0) {
    if ((n & 1) == 1)
      bits += 1
    n >>= 1
  }
  bits
} 

def spaceDistance(s1: String, s2: String) = 
  numberOfOnes(spacesToBinary(s1) ^ spacesToBinary(s2))

现在,一旦我们丢弃空格,比较小写/大写很容易:

def caseDistance(s1: String, s2: String) = {
  val ns1 = s1 filter (_ != ' ')
  val ns2 = s2 filter (_ != ' ')
  (ns1 zip ns2).foldLeft(0){(acc, pair) => acc + (if (pair._1 == pair._2) 0 else 1)}
}

所以,Levenshtein的距离是:

def levenshtein(s1: String, s2: String) = spaceDistance(s1, s2) + caseDistance(s1, s2)

我们还知道关于Levenshtein距离的以下属性.假设d(x,y)是x和y之间的Levenshtein距离.然后我们知道:

d(x, y) = 0 if, and only if, x = y
d(x, y) = d(y, x)
d(x, y) + d(y, z) >= d(x, z)

我称之为triange不等式的最后一个标准.简单地说,从x到z的路径至少与从x到y的路径加上从y到z的路径一样小(想想一个带有顶点x,y和z的三角形).

好的,让我们考虑一下奖金问题.

两个单词之间有多少条路径？好吧,如果Levenshtein距离是n,那意味着你有"n"个独特的修改,a1,a2,...,an.对于这些修改的每个不同顺序,您都有一条路径."n"元素的排列数是"n"(或n!)的阶乘:

def factorial(n: Int): Int = n match {
  case 0 => 1
  case _ => n * factorial(n-1)
}

2! = 2
3! = 6
4! = 24
5! = 120
etc

有"中心"组合吗？实际上,没有.如果我们回过头来想象组合是表示空格/无空格和低/大写的二进制数对,那么很明显你可以简单地反转这些位以产生一个新的组合,其与所选择的组合的距离是最大可能.

或者,换句话说,对于n个字母的每个组合,存在一个且仅一个对应的组合,使得两个组合之间的Levenshtein距离是2*n-1,即任意两个组合之间的最大可能距离.

我看到我忘了计算与s的最小距离为n的所有组合.好吧,我们知道每个组合可以表示为两个二进制数,表示每个字母的空格和大小写,第一个是n-1个数字长,第二个是n个数字长.

我们也知道我们可以简单地反转任何这些"数字"以获得差异.因此,如果我们得到一个2*n - 1位长的大二进制数,并且我们枚举其所有数字,则距离它最小距离d的组合由大小组中的2*n-1个数字的组合给出"d"没有重复.对于N = 2*n-1,这种组合的数量是N!/((Nd)!*d!).

例如,对于距离2和"辅助",n = 4,d = 2,N = 2*4-1 = 7,组合数为7!/(5!*2!)= 7*6/2 = 21.

我们可以这样组合组合:

def computeCombinations(n: Int, d: Int): List[List[Int]] = {
  def gen(d: Int, l: List[Int]): List[List[Int]] = d match {
    case 0 => List(List())
    case _ => for(el <- l;
                  sl <- gen(d-1, l.dropWhile(_ != el).tail))
              yield el :: sl
  }

  gen(d, (0 until n).toList)
}

这将返回要更改的字母/空格列表.我们通过我们想要切换的位数来指示哪个字母或空格需要改变.为简化起见,我们假设大写的二进制数和空格/无空格的二进制数在一个二进制数中连接.

接下来,我们必须找到一种方法来从这些信息中产生变化.大写/小写很简单,假设我们收到没有空格的单词:

def toggleCharCase(c: Char) = (c ^ ('A' ^ 'a')).toChar
def toggleCases(s: String, bits: List[Int]) = (
  s.zipWithIndex
  map (t => if (Set(bits: _*) contains t._2) (toggleCharCase(t._1), t._2) else t)
  map (_._1)
)

切换空间更加困难.我们将使用上面定义的spacesToBinary将其转换为设置的位数列表,切换请求的位并返回该位.之后,我们使用不同的函数将空格插入适当的位置:

def toggleSpaces(s: String, bits: List[Int]): List[Int] = {
  val before = spacesToBinary(s)
  val beforeBits = Set() ++ 
                   (for(i <- 0 to 30; // Assuming 32 bits, 1 for sign
                        if (scala.Math.pow(2, i).toInt & before) != 0)
                    yield i)
  val afterBits = (beforeBits union Set(bits: _*)) diff 
                  (beforeBits intersect Set(bits : _*))
  afterBits.toList
}

def addSpaces(s: String, bits: List[Int]): String = (
  s.filter(_ != ' ').zipWithIndex 
  map (t => t._1.toString + (if (bits contains t._2) " " else ""))
  mkString
)

现在我们必须计算空间差异,删除空格,切换案例,然后再添加空格.让我们来看看:

def changeCombination(s: String, n: Int, bits: List[Int]) = {
  // Split the binary number with all changes into case changes and space changes
  val spaceBits = bits filter (_ >= n) map (_ - n)
  val caseBits = bits filter (_ < n)

  // Compute the set of spaces after changing them
  val newSpaces = toggleSpaces(s, spaceBits)

  // Remove spaces and toggle case
  val noSpaces = s filter (_ != ' ')
  val caseChanged = toggleCases(noSpaces, caseBits).mkString

  // Now add the spaces as computed before
  val spacesAdded = addSpaces(caseChanged, newSpaces).mkString
  spacesAdded
}

最后,我们计算所有组合,然后为每个组合生成一个修改过的字符串:

def makeCombinations(s: String, d: Int) = {
  val n = (s filter (_ != ' ')).length
  for(combination <- computeCombinations(n*2-1, d))
  yield changeCombination(s, n, combination)
}

此代码已在Scala 2.8上进行了测试(除了我刚刚制作的一些重命名).以下是运行的结果:

scala> makeCombinations("ai ds", 2) foreach println
AI ds
Ai Ds
Ai dS
A i ds
Aids
Ai d s
aI Ds
aI dS
a I ds
aIds
aI d s
ai DS
a i Ds
aiDs
ai D s
a i dS
aidS
ai d S
a ids
a i d s
aid s