Поиск всех возможных комбинаций значений между двумя массивами

У меня есть два массива строк, не обязательно одинаковой длины, я хочу найти все возможные «наборы» комбинаций между двумя значениями из массивов, без повторов из любого массива.
Например, учитывая массивы:
{ "A1", "A2", "A3" }
{ "B1", "B2" }
The result I want is the following sets:
{ ("A1", "B1"), ("A2", "B2") }
{ ("A1", "B1"), ("A3", "B2") }
{ ("A1", "B2"), ("A2", "B1") }
{ ("A1", "B2"), ("A3", "B1") }
{ ("A2", "B1"), ("A3", "B2") }
{("A2", "B2"), ("A3", "B1")}

Мое общее направление - создать рекурсивную функцию, которая принимает в качестве параметра два массива и удаляет каждую "выбранную" строку за раз , вызывая себя до тех пор, пока любой из массивов не станет пустым, однако меня беспокоят проблемы с производительностью (мне нужно запустить этот код примерно на 1000 пар строковых массивов).
Может ли кто-нибудь направить меня к эффективному методу для этого?