這裏是一個工作版本。請參閱代碼中的註釋:
package strong;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Strong {
/**
* Are item1 and item2 strongly linked ?
* @param item1 the first item for example "abc"
* @param item2 the second item for example "hij"
* @param groups example: [[nop], [tuv, klm], [qrs, abc], [abc, def, hij],
* [hij, klm]]
* @return true if item1 and item2 are strongly linked
*/
public static boolean stronglyLinked(String item1, String item2,
Collection<Set<String>> groups) {
// true if groups contains a set with item1 and item2
return groups.stream().
anyMatch(g-> g.contains(item1) && g.contains(item2));
}
/**
* Are item1 and item2 weakly linked ?
* @param item1 the first item for example "abc"
* @param item2 the second item for example "hij"
* @param groups example: [[nop], [tuv, klm], [qrs, abc], [abc, def, hij],
* [hij, klm]]
* @return true if item1 and item2 are weakly linked
*/
public static boolean weaklyLinked(String item1, String item2,
Collection<Set<String>> groups) {
// call private implementation with bag parameter (to avoid infinite
// recursion).
return weaklyLinked(item1, item2, groups, new HashSet());
}
/**
* Get strongly and weakly link count for the given item
* @param itemId the item
* @param orderHist for example: {"first:abc","first:hij", "second:hij",
* "second:klm", "third:nop","fourth:qrs", "fourth:abc", "first:def",
* "fifth:klm", "fifth:tuv"}
* @return an array with [0] => strongly linked count, [1] => weakly linked
* count.
*/
public static int[] getLinkCount(String itemId, String[] orderHist) {
// get groups of items bought together for example:
// [[nop], [tuv, klm], [qrs, abc], [abc, def, hij], [hij, klm]]
final Collection<Set<String>> groups = Arrays.stream(orderHist).
map(o-> o.split(":")).
// for example map "first:abs" to ["first", "abc"]
collect(Collectors.groupingBy(o-> o[0],
Collectors.mapping(o-> o[1], Collectors.toSet()))).
values();
// group by customerId but keep only values (groups are
// important but customer are not).
// get the set of strongly linked items
final Set<String> stronglyLinkedItems = groups.stream().
flatMap(g-> g.stream()).
// we get someting like: [nop, tuv, klm, qrs, abc, abc, def,
// hij]
filter(item-> !item.equals(itemId)).
// select only item != itemId
distinct().
// optimization. but stronglyLinked is not so costly (so may be
// removed)
filter(item-> stronglyLinked(item, itemId, groups)).
// select only item strongly linked with item
collect(Collectors.toSet());
// make a set from that stream
// weeklyLinked items
final Set<String> weaklyLinkedItems = groups.stream().
flatMap(g-> g.stream()).
// we get someting like: [nop, tuv, klm, qrs, abc, abc, def,
// hij]
filter(item-> !item.equals(itemId)).
// select only item != itemId
filter(item-> !stronglyLinkedItems.contains(item)).
// remove strongly linked items (alreay in stronglyLinkedItems
// set).
distinct().
// remove duplicate. it's only an optimization we don't want
// to compute costly weaklyLinked() on duplicate (not needed).
filter(item-> weaklyLinked(item, itemId, groups)).
// select only item weakly linked with itemId
collect(Collectors.toSet());
// make a set
// return the result array
return IntStream.of(
stronglyLinkedItems.size(),
weaklyLinkedItems.size()).
toArray();
}
/**
* main
*/
public static void main(String[] args) {
final String orderHist[] = {
"first:abc","first:hij", "second:hij", "second:klm", "third:nop",
"fourth:qrs", "fourth:abc", "first:def", "fifth:klm", "fifth:tuv"};
int[] result = getLinkCount("abc", orderHist);
System.out.println(result[0]);
System.out.println(result[1]);
}
private static boolean weaklyLinked(String item1, String item2,
Collection<Set<String>> groups, Set<Set<String>> bag) {
// if (item1, item2) has already been explored then return false
// this is needed to avoid infinite recursion
if (bag.stream().anyMatch(s-> s.contains(item1) && s.contains(item2))) {
return false;
}
// add (item1, item2) to the bag
bag.add(Stream.of(item1, item2).collect(Collectors.toSet()));
return groups.stream().
flatMap(g-> g.stream()).
// we get someting like:
// [nop, tuv, klm, qrs, abc, abc, def, hij]
filter(item-> !item.equals(item1) && !item.equals(item2)).
// filter for removing item1 and item2 from the stream
anyMatch(item-> (stronglyLinked(item1, item, groups) ||
weaklyLinked(item1, item, groups, new HashSet(bag))) &&
(stronglyLinked(item2, item, groups) ||
weaklyLinked(item2, item, groups, new HashSet(bag))));
// any item strongly or weakly linked with item1 and item2 =>
// if yes return true
}
}
我知道這味道聞起來像一個遞歸解決方案....如果你訪問一個IDE我將不勝感激一些代碼提示...反正也讓我在這方面努力。 – codeNinja