如果子集共享共同价值，则将子集组合成更大的集

Question

我正在尝试创建一种方法，该方法将 return 具有邻居的最大卡片集。例如，如果我有 list<RANK> rankList = [FIVE, QUEEN, KING, ACE, TEN]，它将 return [KING, ACE, QUEEN]。我还没有完全实现它，但是我得到了将一组分成多个较小的组的部分。

private boolean isStraight(List<Card> cards) {
        Set<RANK> rankList = cards.stream()
            .map(Card::getRank)
            .distinct()
            .collect(Collectors.toSet());


        List<Set<RANK>> subSets = new ArrayList<>();

        for(RANK rank : rankList) {
            int currRankValue = rank.getValue();
            RANK prevRank = RANK.getRank(currRankValue - 1);
            RANK nextRank = RANK.getRank(currRankValue + 1);

            if(!subSets.stream().anyMatch(set -> set.contains(rank))) {
                Set<RANK> newSet = new HashSet<>();
                newSet.add(rank);
                subSets.add(newSet);
            }

            subSets.stream()
                .filter(set -> (set.contains(prevRank) || set.contains(nextRank)))
                .forEach( set -> set.add(rank));
        }

        System.out.print(subSets);
        return false;
    }

Card.java:

 public static enum RANK {
        NONE(0),
        TWO(2), THREE(3), FOUR(4), FIVE(5),
        SIX(6), SEVEN(7), EIGHT(8), NINE(9),
        TEN(10), JACK(11), QUEEN(12), KING(13), ACE(14);

        private final int value;

        private RANK(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static RANK getRank(int value) {
            for(RANK r : RANK.values() ) {
                if (r.getValue() == value)
                    return r;
            }
            return NONE;
        }
    }

在我检查是否有 5 张或更多张牌可以形成顺子之前，我已经组合了至少具有一个共同值的子集。我该怎么做？我想不出任何不涉及很多循环的东西。

已编辑

添加了整个Card.java:

ppackage deck;

public class Card implements Comparable {

    public static enum SUIT {
        SPADES,
        HEARTS,
        CLUBS,
        DIAMONDS
    }

    public static enum RANK {
        NONE(0),
        TWO(2), THREE(3), FOUR(4), FIVE(5),
        SIX(6), SEVEN(7), EIGHT(8), NINE(9),
        TEN(10), JACK(11), QUEEN(12), KING(13), ACE(14);

        private final int value;

        private RANK(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static RANK getRank(int value) {
            for(RANK r : RANK.values() ) {
                if (r.getValue() == value)
                    return r;
            }
            return NONE;
        }
    }

    private final RANK rank;
    private final SUIT suit;

    public Card(RANK rank, SUIT suit) {
        this.rank = rank;
        this.suit = suit;
    }

    public RANK getRank() {
        return rank;
    }

    public SUIT getSuit() {
        return suit;
    }

    @Override
    public String toString() {
        return "Card{" +
            "rank=" + rank +
            ", suit=" + suit +
            '}';
    }

    @Override
    public int compareTo(Object that) {
        return this.rank.getValue() - ((Card) that).rank.getValue();
    }
}

已编辑

添加了带循环的解决方案：在方法中 return 之前添加这个。

for(int index = 0; index < subSets.size(); index++) {
           for(int index2 = 1; index2 < subSets.size(); index2++) {
               if(!Collections.disjoint(subSets.get(index), subSets.get(index2)) && index != index2) {
                    subSets.get(index).addAll(subSets.remove(index2));
                    index2--;
               }
           }
       }

Answer 1

（我仍然对 java 函数式 API 的编码风格有问题。）我会使用不同的排序流，并使用列表来制作子列表。不同的列表被分成连续等级的子列表。我希望看到 flatMap、reduce 或其他更好的解决方案。

static boolean isStraight(List<Card> cards) {
    List<List<Rank>> rankList = cards.stream()
            .map(Card::getRank)
            .sorted(Comparator.comparingInt(Rank::getValue))
            .distinct()
            .collect(LinkedList::new,
                    (list, rank) -> {
                        boolean startNextList = false;
                        if (list.isEmpty()) {
                            startNextList = true;
                        } else {
                            List<Rank> priorRanks = list.get(list.size() - 1);
                            if (priorRanks.get(priorRanks.size() - 1).getValue()
                                       < rank.getValue() - 1) {
                                startNextList = true;
                            }
                        }
                        if (startNextList) {
                            List<Rank> priorRanks = new LinkedList<>();
                            list.add(priorRanks);
                        }
                        List<Rank> priorRanks = list.get(list.size() - 1);
                        priorRanks.add(rank);
                    },
                    (list1, list2) -> {
                        list1.addAll(list2);
                    });

转储：

    rankList.stream().forEach((list) -> {
        System.out.printf("# %d - ", list.size());
        list.stream().forEach((r) -> System.out.printf("%s, ", r));
        System.out.println();
    });
    ...

Answer 2

假设一个“直线”由五个相邻的RANK组成，我们不要想的太复杂，只要测试是否找到这样的范围即可：

boolean isStraight(List<Card> cards) {
    BitSet set=cards.stream().map(Card::getRank).mapToInt(Card.RANK::ordinal)
        .collect(BitSet::new, BitSet::set, BitSet::or);
    for(int s=set.nextSetBit(0), e; s>=0; s=set.nextSetBit(e)) {
        e=set.nextClearBit(s);
        if(e-s >= 5) return true;
    }
    return false;
}

此代码未绑定到特定的手尺寸，可以轻松适应其他直尺寸。

处理 ordinal() 和 BitSet 可能看起来有点低级，我真的希望有一个使用 EnumSet 或 EnumMap 的解决方案，就像然而，这些更高级别的类在这里并没有太大帮助（他们甚至没有实现 SortedSet/SortedMap）…

请注意，此方法 returns a boolean 作为您问题中的代码。所以它不关心哪些实际牌组成了顺子。 Afaik，在大多数扑克变体中，这确实无关紧要。

然而，从字面上看你的问题介绍，得到“有邻居的最大卡片集”可以按如下方式完成：

Set<Card> largestStraightCandidate(List<Card> cards) {
    BitSet set=cards.stream().map(Card::getRank).mapToInt(Card.RANK::ordinal)
        .collect(BitSet::new, BitSet::set, BitSet::or);
    int min=0, max=0;
    for(int s=set.nextSetBit(0), e; s>=0; s=set.nextSetBit(e)) {
        e=set.nextClearBit(s);
        if(e-s >= max-min) {
            min=s;
            max=e;
        }
    }
    if(max==min) return Collections.emptySet();// cards was empty
    Card.RANK[] all=Card.RANK.values();
    EnumSet<Card.RANK> rankSet=EnumSet.range(all[min], all[max-1]);
    return cards.stream().filter(card-> rankSet.contains(card.getRank()))
      .collect(Collectors.toSet());
}

不同之处在于，我们现在会记住最大的范围，而不是在找到足够大的范围后返回。然后，我们通过过滤该范围内所有卡片的原始卡片列表来重构卡片。

这意味着

对于多个最大集合，由于BitSet的循环，将返回排名较高的集合，即列表中的顺序无关紧要
如果范围内存在多张相同RANK的牌，则全部包含在Card的Set中；不要使用它的大小来决定直线的大小，您必须首先转换为 RANK 的 Set，或者，如果您仔细查看代码，您会看到 [= RANKs 的 22=] 已经存在 before 构建 Cards 的 Set…

Answer 3

考虑到可能的直道很少，您是否考虑过一种更简单的方法，即预先计算所有直道？

// using .ordinal() instead of .value to keep it short.  
// Shouldn't be too hard to change it to use values
final Set<EnumSet<RANK>> STRAIGHTS = EnumSet.range(TWO, TEN).stream()
        .map(rank -> EnumSet.range(rank, RANK.values()[rank.ordinal() + 4]))
        .collect(toSet());

然后

boolean isStraight(List<Card> cards) {
    EnumSet<RANK> ranks = cards.stream()
        .map(Card::getRank)
        .collect(toCollection(() -> EnumSet.noneOf(RANK.class)));

    return STRAIGHTS.contains(ranks);
}

Answer 4

我关注的是与 "largest set of cards which has neighbors." 相关的问题如果对卡片等级值列表进行排序，这将变成分割列表运行的问题，然后从这些片段中选择最长的运行(s)。

精明的读者会注意到 . I'll use a technique similar to 与该问题的相似之处。

首先，让我们从包含 OP 示例中的输入列表开始。不过，以下技术应该适用于任何输入。

    List<Rank> rankList = [FIVE, QUEEN, KING, ACE, TEN];

让我们排序并使此列表具有唯一元素：

    List<Rank> sorted = rankList.stream()
        .distinct()
        .sorted()
        .collect(toList());

[FIVE, TEN, QUEEN, KING, ACE]

现在让我们计算列表应该被拆分的位置，以分隔运行个连续排名值。这发生在列表中彼此相邻的值不是连续排名值的位置。我们通过索引列表（从 1 开始）并通过检查列表中的相邻值来过滤索引来做到这一点：

    List<Integer> splits = IntStream.range(1, sorted.size())
        .filter(i -> sorted.get(i).ordinal() != sorted.get(i-1).ordinal() + 1)
        .boxed()
        .collect(toCollection(ArrayList::new));

[1, 2]

这些是运行之间的位置。这几乎足以创建子列表的信息，但它省略了第一个子列表的开头和最后一个子列表的结尾的索引。要添加这些，我们只需在前面添加 0 并在末尾添加 size 即可：

    splits.add(0, 0);
    splits.add(list.size());

[0, 1, 2, 5]

现在我们可以使用每对索引生成包含每个运行:

的子列表

    List<List<Rank>> runs = IntStream.range(1, splits.size())
        .mapToObj(i -> list.subList(splits.get(i-1), splits.get(i)))
        .collect(toList());

[[FIVE], [TEN], [QUEEN, KING, ACE]]

我们可以找到最长的运行，然后打印出与其长度匹配的运行：

    int longest = runs.stream()
        .mapToInt(list -> list.size())
        .max()
        .getAsInt();
    runs.stream()
        .filter(list -> list.size() == longest)
        .forEach(System.out::println);

[QUEEN, KING, ACE]

综合起来，我们有：

static void split(List<Rank> rankList) {
    List<Rank> sorted = rankList.stream()
        .distinct()
        .sorted()
        .collect(toList());

    List<Integer> splits = IntStream.range(1, sorted.size())
        .filter(i -> sorted.get(i).ordinal() != sorted.get(i-1).ordinal() + 1)
        .boxed()
        .collect(toCollection(ArrayList::new));

    splits.add(0, 0);
    splits.add(sorted.size());

    List<List<Rank>> runs = IntStream.range(1, splits.size())
        .mapToObj(i -> sorted.subList(splits.get(i-1), splits.get(i)))
        .collect(toList());

    int longest = runs.stream()
        .mapToInt(list -> list.size())
        .max()
        .getAsInt();

    runs.stream()
        .filter(list -> list.size() == longest)
        .forEach(System.out::println);
}

如果子集共享共同价值，则将子集组合成更大的集

Combining sub sets to larger sets if they share common value

java

set

java-8

java-stream