5

假设我有一组字符[ABC]。我正在寻找一个正则表达式，它可以匹配除了空集之外的超集的任何排列，即

ABC ACB BAC BCA CAB CBA
AB BC AC CB CA BA
A B C

正则表达式应该（显然）不匹配空字符串。

ps 表达相同目标的另一种方法是“最多匹配包含集合中每个字符的任何非空字符串一次”。

更新：集合[ABC]只是一个例子，真实的集合也可能更大。带着这个问题，我希望找到一个“通用”的解决方案，而不是针对[ABC].

4

8 回答 8

6

我相信这可以通过正则表达式来解决。使用这个正则表达式：

/^([ABC])(?!\1)([ABC])?(?!\1|\2)[ABC]?$/

如果您需要在线演示，请告诉我。

于 2012-04-26T12:08:44.647 回答
3

感谢您的回答（尤其是 anubhava 和 codaddict 的），我能够找到这个解决方案，我认为它非常优雅，因为它只允许输入一次集合：

\b(([ABC])(?!.*\2))+\b

\b需要匹配完整的单词；省略它们也会找到尊重所需属性的子词。要匹配一个完整的字符串，你显然会这样做：

^(([ABC])(?!.*\2))+$
于 2012-04-26T20:34:40.080 回答
1

这不是正则表达式擅长的。您可能只想创建一个排列列表，然后生成所有唯一的子字符串。

就像是：

def matches(s, characters):
    if len(s) != len(set(s)):
        return False # not unique sequence of characters
    return set(s).issubsetof(set(characters))
于 2012-04-26T12:02:15.537 回答
1

尝试：

([ABC]?)(?!.*\1)([ABC]?)(?!.*\2)[ABC]?

它只是[ABC]?重复了 3 次，并添加了对不允许重复字符的否定前瞻断言的检查。

请注意，这仅在输入集都是唯一的情况下才有效。

看它工作

于 2012-04-26T12:05:54.210 回答
1 
"A((B?C?)|(C?B?))|B((A?C?)|(C?A?))|C((A?B?)|(B?A?))"

它是 A|B|C，它们中的每一个都可以跟一对可选值

 A(B?C?) matches A, AB,AC and ABC
 A(C?B?) matches A, AC,AB and ACB

但不是 ACAC、AA 或 ACC。以 B 或 C 作为第一个字符的情况是等价的。

对于更长的字符串，这很快就会变得丑陋。更好的方法是（伪代码）：

 string.sort().matches ("^A?B?C?$") && string.length > 0
于 2012-04-26T13:06:56.043 回答
0

好的，我必须说我已经考虑了很多你的问题 - 因为你似乎想要一些真正通用和可定制的东西（支持尽可能多的元素等） - 这是我认为最优化的解决方案。

从数学的角度来看，您想要的是识别一组元素的所有排列而不重复。

步骤1 ：

找到集合的所有排列，重复（并将它们存储在一个数组中）

[ABC]([ABC]{1,2})?

旁注：假设您有一个包含n元素的集合，您所要做的就是：

[elements]([elements]{1,n-1})?

第2步 ：

过滤所有具有重复元素的排列

PHP 中的示例代码：

<?php

    function strToArray($str)
    {
        $i = 0;

        while (isset($str[$i]))
        {
            $result[$i] = $str[$i];
            $i++;
        }

        return $result;
    }

    function noDuplicates($str)
    {
        if (array_unique(strToArray($str))==strToArray($str)) return true;
        else return false;
    }

    $AAA = "AAA";
    $ABC = "ABC";

    if (noDuplicates($AAA)) echo "$AAA : ok"; else echo "$AAA : not ok\n";
    if (noDuplicates($ABC)) echo "$ABC : ok"; else echo "$ABC : not ok\n";

?>

输出 ：

AAA : not ok
ABC : ok
于 2012-04-27T08:16:45.497 回答
0

这是我的版本：

\b(?=[ABC]{1,3})([ABC]{1})(?:(?!\1)([ABC]{1})(?:(?!\1)(?!\2)[ABC]{1})?)?\b

逻辑：

  • \b: 寻找单词边界
  • (?=[ABC]{1,3}): 前瞻看看是否有一个长度 = 3 的字符串，其值只有 A、B、C
  • ([ABC]{1}): 匹配第一个字符然后可选
  • (?!\1)([ABC]{1})：检查下一个字符是否与先前匹配的不同 - 如果不是，则匹配它并可选
  • (?!\1)(?!\2)[ABC]{1}: 检查下一个字符是否与之前匹配的字符 1 或 2 不同 - 如果不是，则匹配该字符

我针对这个输入进行了测试，所以它看起来很可靠：

AABCC BBCC AB BC AC CB CA BA ABC ABC ACB BAC BCA CAB CBA AAA ABB AAA BBC AA

编辑：

正如您提到的，字符集可以更大，我会按照您问题中的 PS 建议并按照以下方式执行此操作：

  • 引入chars数组，它将保存允许集中的每个字符（将字符串拆分为字符）

  • 得到一个数组inputStrings（在空格或其他任何需要的地方分割输入字符串）

  • 对于 {string中的每个inputStrings

  • 检查是否string.length <= inputStrings.length
  • 尝试将列表中的每个字符与当前输入匹配，并保存在matches列表中找到的匹配数
  • 检查matches列表是否包含任何条目，然后检查所有条目是否 == 1 或 0 }
于 2012-04-26T12:23:32.470 回答
0

试试这个：（更新）

A[BC](?![ABC])|B[AC](?![ABC])|C[AB](?![ABC])|[ABC](?![ABC])|(ABC|ACB|BAC|BCA|CAB|CBA)(?![ABC])

演示：

http://regexr.com?30pa6

于 2012-04-26T11:57:44.440 回答