ごめん、質問をちゃんと見てなかったわ
これでおｋ
長すぎるって怒られたから改行しといた

(?:犬.*(?:(猫)?.*鳥.*牛.*(?(1)|猫)|(鳥)?.*猫.*牛.*(?(2)|鳥)|牛.*(?:猫.*鳥|鳥.*猫))|
猫.*(?:(鳥)?.*牛.*犬.*(?(3)|鳥)|(牛)?.*鳥.*犬.*(?(4)|牛)|犬.*(?:鳥.*牛|牛.*鳥))|
鳥.*(?:(牛)?.*犬.*猫.*(?(5)|牛)|(犬)?.*牛.*猫.*(?(6)|犬)|猫.*(?:牛.*犬|犬.*牛))|
牛.*(?:(犬)?.*猫.*鳥.*(?(7)|犬)|(猫)?.*犬.*鳥.*(?(8)|猫)|鳥.*(?:犬.*猫|猫.*犬)))