Find unique variants of a product

Question

I am writing a piece of code that returns all the unique variants that a product is available in for an ecommerce app. For example, a shirt product can be available in different colors, sizes, and linen. If the available attributes are red, green, L, XL, Cotton, and Polyester, then a list of the unique variants should be eventually returned as:

[{red; L; Cotton} ; {red; L; Polyester} ; {red; XL; Cotton} ; {red; XL; Polyester} ; {green; L; Cotton} ; {green; XL; Cotton} ; {green; L; Polyester} ;

{green; XL; Polyester}]

This would be the unique variants available for the product.

The code below works and eventually returns a string list of IDs representing each variant available for the product. The only problem that I am having with this is that it generates a duplicate of each variant. I can easily take care of that with a Set.ofList function after this code runs, but would like to solve that problem here internally. I'm new to F#, so what can I do to optimize this code?

type NewProductAttributeInfo = {
    AttributeId : string;
    AttributeCategoryId : string
}


let rec private returnVariant (curIdx: int) (listLength: int) 
    (attList: (int * NewProductAttributeInfo * NewProductAttributeInfo) list) 
    (curList: NewProductAttributeInfo list) =

    match curList with
    | x when x.Length = listLength -> curList
    | x -> 
        let attTup =
            attList
            |> List.filter (fun x' -> 
                                let idx1,att1,att2' = x'
                                idx1 >= curIdx && not(curList 
                                                        |> List.exists (fun x'' -> 
                                                                            x'' = att2'))
                            )
        let idx1,att1,att2 = attTup |> List.head
        let newList = curList @ [att2]
        returnVariant idx1 newList.Length attList newList


let rec calculateVariants (attList: NewProductAttributeInfo list) 
    (currentList: (int * NewProductAttributeInfo * NewProductAttributeInfo) list) =

    // group attribute list by category id
    let attGrouped = attList |> List.groupBy (fun x -> x.AttributeCategoryId)
    let (firstGroupCatId,firstGroupDetails) = attGrouped.[0]




    match currentList with
    | [] ->
        let rawVariants = [for nxt in 0 .. (attGrouped.Length - 1) do
                            if nxt > 0
                            then
                                // begin iteration
                                for d in firstGroupDetails do
                                    let _,det = attGrouped.[nxt]
                                    for det' in det do
                                        yield (nxt, d, det')
                        ]
        calculateVariants attList rawVariants
    | x ->
        let groupLength = x |> List.groupBy (fun (idx,d0,nxtD) -> idx)
                        |> List.length |> ((+)1)
        let sortedGroup = x |> List.sortBy (fun (x,y,z) -> x)
        if groupLength > 2
        then // below is the block that generates the duplicates
            [for att in sortedGroup do
                for attCompare in sortedGroup do
                    let idx1,att1,att2 = att
                    let idx2,attC1,attC2 = attCompare
                    if idx2 > idx1 && att2 <> attC2
                    then
                        let idString = 
                            returnVariant idx2 groupLength x [att1; att2; attC2]
                            |> List.map (fun nl -> nl.AttributeId)
                        yield String.concat "," idString
            ]
        else
            [
                for att in sortedGroup do
                    let idx1,att1,att2 = att
                    let idString = 
                            returnVariant idx1 groupLength x [att1; att2]
                            |> List.map (fun nl -> nl.AttributeId)
                    yield String.concat "," idString
            ]

Answer 1

If I understand correctly, you're looking for the Cartesian product of the attributes in each attribute category.

To get the Cartesian product, I've adapted* Eric Lippert's solution from his blog post Computing a Cartesian product with LINQ.

let cartesianProduct xs =
    Seq.fold (fun acc xs -> seq {
        for accSeq in acc do
        for x in xs do
        yield Seq.append accSeq (Seq.singleton x)
    }) (Seq.singleton Seq.empty) xs

Then we need to group by the attribute category, and pull out just the attributes**.

let variants (attributes : seq<NewProductAttributeInfo>) =
    attributes
        |> Seq.groupBy (fun attribute -> attribute.AttributeCategoryId)
        |> Seq.map (snd >> Seq.map (fun attribute -> attribute.AttributeId))
        |> cartesianProduct

Here is a test on the sample data you provided

let attributes = [
    { AttributeId = "red"; AttributeCategoryId = "Color" };
    { AttributeId = "L"; AttributeCategoryId = "Size" };
    { AttributeId = "XL"; AttributeCategoryId = "Size" };
    { AttributeId = "Cotton"; AttributeCategoryId = "Material" };
    { AttributeId = "green"; AttributeCategoryId = "Color" };
    { AttributeId = "Polyester"; AttributeCategoryId = "Material" }
]

for variant in variants attributes do
    printfn "%A" variant

Which gives:

seq ["red"; "L"; "Cotton"]
seq ["red"; "L"; "Polyester"]
seq ["red"; "XL"; "Cotton"]
seq ["red"; "XL"; "Polyester"]
seq ["green"; "L"; "Cotton"]
seq ["green"; "L"; "Polyester"]
seq ["green"; "XL"; "Cotton"]
seq ["green"; "XL"; "Polyester"]

---

* Hopefully without introducing errors.

** This is a little bit nicer in C# since we have the overload of GroupBy that takes an elementSelector parameter:

return attributes.GroupBy(attribute => attribute.CategoryId, attribute => attribute.Id)
    .CartesianProduct();

Answer 2

As requested, this is a modification of mjolka's answer to use list instead of seq. Originally, I assumed this is going to be more efficient, because enumerating Seq.append accSeq (Seq.singleton x) would be \$O(n^2)\$ (just like Enumerable.Concat(accSeq, new[] { x })).

But if I understand the source of Seq.append correctly, it's actually smart enough to stay \$O(n)\$, so my modification is not likely to bring much benefit.

let cartesianProduct xs =
    List.foldBack (fun xs acc -> [
        for accSeq in acc do
        for x in xs do
        yield x::accSeq
    ]) xs [[]]

let variants (attributes : list<NewProductAttributeInfo>) =
    attributes
        |> List.groupBy (fun attribute -> attribute.AttributeCategoryId)
        |> List.map (snd >> List.map (fun attribute -> attribute.AttributeId))
        |> cartesianProduct